代码模板-树状数组

树状数组基于二进制拆分，用 $c[i]$ 维护以 $i$ 结尾、长度为 $lowbit(i)$ 的区间 $[i-lowbit(i)+1,\,i]$ 的和。树深 $O(\log n)$ ，修改与查询均为 $O(\log n)$ 。

1	#define lowbit(x) ((x)&(-(x)))

单点修改 + 区间查询（维护前缀和）

const int N = 5e5 + 5;
int c[N], n;

void add(int id, int x) {        // 单点修改：a[id] += x
    for (int i = id; i <= n; i += lowbit(i)) c[i] += x;
}

int query(int id) {              // 前缀查询：sum(a[1..id])
    int ans = 0;
    for (int i = id; i > 0; i -= lowbit(i)) ans += c[i];
    return ans;
}

int query(int l, int r) {        // 区间查询：sum(a[l..r])
    return query(r) - query(l - 1);
}

把树状数组当桶用（权值树状数组），即可统计比某数小的个数，用于求逆序对等。值域大时先离散化。

区间修改 + 单点查询（差分）

维护差分数组 $b[i]=a[i]-a[i-1]$ ，则 $a[id]=\sum_{j=1}^{id} b[j]$ 。

int c[N], n;

void add(int id, int x) {
    for (int i = id; i <= n; i += lowbit(i)) c[i] += x;
}

void add(int l, int r, int x) {  // 区间修改：a[l..r] += x
    add(l, x), add(r + 1, -x);
}

int query(int id) {              // 单点查询：a[id]
    int ans = 0;
    for (int i = id; i > 0; i -= lowbit(i)) ans += c[i];
    return ans;
}

区间修改 + 区间查询（差分 + 维护 i·b[i]）

由 $\sum_{i=1}^x a[i] = (x+1)\sum_{i=1}^x b[i] - \sum_{i=1}^x i\cdot b[i]$ ，用两个树状数组分别维护 $b[i]$ 与 $i\cdot b[i]$ 。

#define lowbit(x) ((x)&(-(x)))

const int N = 1e6 + 5;
int c1[N], c2[N], n;   // c1 维护 b[i]，c2 维护 i*b[i]

void add(int id, int x) {
    for (int i = id; i <= n; i += lowbit(i)) {
        c1[i] += x;
        c2[i] += id * x;
    }
}
void add(int l, int r, int x) {           // 区间修改：a[l..r] += x
    add(l, x), add(r + 1, -x);
}
int query1(int id) {                       // S1 = sum(b[1..id])
    int s = 0;
    for (int i = id; i; i -= lowbit(i)) s += c1[i];
    return s;
}
int query2(int id) {                       // S2 = sum(i*b[i], i=1..id)
    int s = 0;
    for (int i = id; i; i -= lowbit(i)) s += c2[i];
    return s;
}
int query(int id) {                        // 前缀和 sum(a[1..id])
    return (id + 1) * query1(id) - query2(id);
}
int query(int l, int r) {                  // 区间查询 sum(a[l..r])
    return query(r) - query(l - 1);
}

相关笔记：【数据结构】树状数组学习笔记