NOI 一轮复习：树状数组

又称 Fenwick 树、二叉索引树（BIT）。支持维护前缀后缀的信息。

概述

树状数组将序列拆分成了恰好 $n$ 个区间，对于每一个前缀求解都可以拆成 $\log p$ 个区间进行求解，而且自带一个卡不掉的 $1/2$ 的常数，随机数据下则为 $1/4$ 的常数！我们通过 $\operatorname{lowbit}$ 来支持树状数组的工作。

一个显式的树状数组

模板，区间和我们可以用前缀和相减来求解，代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long i64; 

int n, m; 
int a[500005]; i64 C[500005]; 

void add(int x, int k) { for (; x <= n; x += x & -x) C[x] += k; }
i64 sum(int x) { i64 r = 0; for (; x; x -= x & -x) r += C[x]; return r; }

int main(void) {
    scanf("%d%d", &n, &m); 
    for (int i = 1; i <= n; ++i) scanf("%d", a + i), add(i, a[i]); 
    while (m--) {
        int op, x, y; scanf("%d%d%d", &op, &x, &y); 
        if (op == 1) add(x, y); 
        else printf("%lld\n", sum(y) - sum(x - 1)); 
    }
    return 0;
}