博客

#include <iostream>
#include <cstring>

using LL = long long;

const int MAXN = 100000000;
int arr[MAXN] = {0};
int tree[MAXN] = {0};

inline int LEFT(int n) {
    return 2 * n;
}

inline int RIGHT(int n) {
    return 2 * n + 1;
}

inline int MID(int l, int r) {
    return l + (r - l) / 2;
}

void build(int l, int r, int p) {
    if (l + 1 == r) {
        tree[p] = arr[l];
        return;
    }
    int mid = MID(l, r);
    int lc = LEFT(p);
    int rc = RIGHT(p);
    build(l, mid, lc);
    build(mid, r, rc);
    tree[p] = tree[lc] + tree[rc];
}

LL query(int ql, int qr, int l, int r, int p) {
    if (qr <= l || ql >= r) {
        return 0;
    }
    if (l >= ql && r <= qr) {
        return tree[p];
    }
    int mid = MID(l, r);
    LL sum = 0;
    if (ql < mid) {
        sum += query(ql, qr, l, mid, LEFT(p));
    }
    if (qr > mid) {
        sum += query(ql, qr, mid, r, RIGHT(p));
    }
    return sum;
}

void update(int delta, int idx, int l, int r, int p) {
    if (l == idx && l + 1 >= r) {
        tree[p] = arr[idx] + delta;
        return;
    }
    int mid = MID(l, r);
    int lc = LEFT(p);
    int rc = RIGHT(p);
    if (idx < mid) {
        build(l, mid, lc);
    }
    if (idx >= mid) {
        build(mid, r, rc);
    }
    tree[p] = tree[lc] + tree[rc];
}

int main() {
    return 0;
}