这一次谈谈树状数组。
        先考虑一个问题，对于一个给定的数组，如何快速地求出其前缀和?
        最通俗的做法是循环求出前n项和，时间复杂度O(n)。如果数组相当大又多次修改其中数据，求和过程时间消耗巨大。
        为了快速求和，可以用树状数组来完成这一操作。树状数组可以维护并快速求出数组前缀和。

        要理解树状数组原理，先介绍lowbit的概念。
        对于任何一个数，设lowbit(x)表示这个数能够整除的最大的2的方幂。容易知道，将x写成二进制后，lowbit(x)表示从右向左第一个1所对应的二进制数。例如，对于二进制数x:

x=1101101100，lowbit(x)=100;
x=1011000，lowbit(x)=1000;
x=1010000，lowbit(x)=10000.
……

        lowbit有一个重要性质:
        给定数x，则对于满足条件x-lowbit(x)<y<x的数均可以在有限次地进行运算y = y + lowbit(y)后，使得y=x。并且其余的y一定不能在有限次的上述运算后得到x。
        例如给定x=101100，则对于y=101001，进行一次运算，得到101010，再进行一次得到101100。
        证明从略。

        那么对于一个数组tree[i]，tree[i]储存所有满足i-lowbit(i)<x<=i的x的和。这个和是易求的。对于一个符合条件的x，由上面的定理，给x作若干次运算。对于每一次合法的运算结果y，都进行tree[y]+=value[x]，这些y中一定有i，从而将所有符合条件的x都计入了tree[i]。由定理又知，其余不符合条件的x一定不会计入tree[i]。记得将tree[i]+=value[i]，就得到完整的求和。
        对1~n的所有数，都进行上述操作，就可以得到tree数组，这就是树状数组。
        下面研究如何用tree数组求前缀和。
        例如求前10110010前缀和([x，y]表示第x到第y元素的和):

tree[10000000]储存[1，10000000]的数的和，
tree[10100000]储存[10000001，10100000]的和，
tree[10110000]储存[10100001，10110000]的和，
tree[10110010]储存[10110001，10110010]的和。

        显然，10110010前缀和就是树状数组中这4项的和。并且这4项的下标都是重复进行运算y = y - lowbit(y)得到的，直到y=0。这样，计算10110010前缀和只需进行4次加法，比进行传统的10110010(=178)次运算相比，效率大大提升。
        为何叫作树状数组?下图给出解释。

        粗体表示树状数组中的值。
        易知lowbit(x)=x&-x，这样就有了树状数组的完整编写思路：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<iostream>

using namespace std;
const int NUM = 1000000;
int op[NUM + 1], tree[NUM + 1] = {0}, n;

void add(int x, int y) {
    for (; x <= n; x += (x & -x))tree[x] += y;
}

int sum(int x) {
    int res = 0;
    for (; x >= 1; x -= (x & -x))res += tree[x];
    return res;
}

int main() {
    cin >> n;
    for (register int i = 1; i <= n; i++) {
        cin >> op[i];
        add(i, op[i]);
    }
    int x;
    cin >> x;
    cout << sum(x) << endl;
    return 0;
}

树状数组进阶

        树状数组能很好地实现单点查询和前缀和维护，但对于区间求改却无能为力，此时多用线段树来代替。其实树状数组也可以进行区间修改。
        开数组c储存原数组差分，差分即：

        用树状数组维护c数组，易知c数组前缀和就是原数组对应元素的值。在修改区间时，只需修改c数组两个点即可。比如需要将[l,r]上的数都加p，只需将c[l]加上p，c[r+1]减去p。结合树状数组即可快速原数组元素值。
        那区间和如何求呢？注意到：

        于是开数组d记录(i-1)c[i]，并用树状数组维护。在修改c数组时同步修改d数组，结合上面公式即可求出区间和。
        这种思路可以使树状数组代替线段树维护区间和，可以过线段树模板题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
#include<cstdio>

#define MAX 100000+5
using namespace std;
long long op[MAX], tree1[MAX] = {0}, tree2[MAX] = {0}, n, m;

inline long long read() {
    char e = getchar();
    while((e < '0' || e > '9') && (e != '-'))e = getchar();
    bool k = false;
    long long s = 0;
    if (e == '-')k = true, e = getchar();
    while (e >= '0' && e <= '9')s = s * 10 + e - '0', e = getchar();
    return k ? -s : s;
}

void add(int x, long long z, long long tree[]) {
    for (int i = x; i <= n; i += (i & -i))tree[i] += z;
}

long long find(int x, const long long tree[]) {
    long long s = 0;
    for (int i = x; i >= 1; i -= (i & -i))s += tree[i];
    return s;
}

int main() {
    n = read(), m = read();
    for (int i = 1; i <= n; i++) {
        op[i] = read();
        if (i == 1)add(1, op[i], tree1), add(1, 0, tree2);
        else add(i, op[i] - op[i - 1], tree1), add(i, (i - 1) * (op[i] - op[i - 1]), tree2);
    }
    for (int i = 0; i < m; i++) {
        int x, a, b, c;
        x = read();
        if (x == 1) {//区间修改
            a = read(), b = read(), c = read();
            add(a, c, tree1), add(a, (a - 1) * c, tree2);
            add(b + 1, -c, tree1), add(b + 1, -c * b, tree2);
        } else {//区间查询
            a = read() - 1, b = read();
            long long s1 = a * find(a, tree1) - find(a, tree2), s2 = b * find(b, tree1) - find(b, tree2);
            cout << s2 - s1 << endl;
        }
    }
    return 0;
}

        树状数组另一个作用是统计当前大于或小于某个数的元素个数，比如下题：

给定一个包含N个整数的数组A = [A1, A2, … AN]，请你计算有多少个子数组B = [Ai, Ai+1, … Aj] (i ≤ j) 满足B中所有整数的和小于K。
1 ≤ N ≤ 100000 -100000 ≤ Ai ≤ 100000

        枚举每一个子数组求和的$O(n^2)$做法一定会TLE，另一个思路是先预处理前缀和，然后从左到右顺次枚举，根据当前的前缀和推算出使子区间和小于k的前缀和范围，然后查找当前有多少前缀和满足这个条件，有几个合法前缀和便有几个合法的子数列。这个过程可以用树状数组维护。
        为了方便起见，先将问题等价转化：将所有数变为其相反数，问题转化为有多少自数列和大于-k。
        求前缀和，然后从左到右枚举。如果当前的前缀和为s，那么合法的前缀和x应满足：

        也就是x < s-k，我们找出之前有多少小于s-k的前缀和就可以了。
        开一个与数据范围一样大的树状数组，每找到一个前缀和q，我们令q处的元素加一，这样对于一个大于q的数p，它的前缀和就增大了一，从而达到计数目的。
        但是，数据范围确实过大（达到10^10）。可以采用离散化的方法：前缀和最多有100000种可能，给它们按照小大顺序重新编号，编号的相对大小就是原数据的相对大小。开100000大小的数组完全是可以的，本题便得以解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<iostream>
#include<map>
#include<algorithm>

using namespace std;
map<long long, int> m;
long long sum[100000 + 5], sumCopy[100000 + 5], tree[100000 + 5] = {0}, ans = 0;
int id = 1, n, k;

int ID(long long x, int l, int r) {//[,)
    if (r == l + 1) {
        if (sumCopy[l] <= x)return m[sumCopy[l]];
        return -1;
    }
    int mid = (l + r) >> 1;
    if (sumCopy[mid] <= x)return ID(x, mid, r);
    return ID(x, l, mid);
}

inline int query(int x) {
    int s = 0;
    for (int i = x; i >= 1; i -= (i & -i))s += tree[i];
    return s;
}

inline void add(int x) {
    for (int i = x; i <= n; i += (i & -i))tree[i]++;
}

int main() {
    ios::sync_with_stdio(false);//关掉同步，加速读入
    cin >> n >> k;
    k = -k;//先对k取相反数
    sumCopy[0] = sum[0] = 0;//copy一下前缀和
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        sumCopy[i] = sum[i] = sum[i - 1] - x;//求前缀和
    }
    sort(sumCopy + 1, sumCopy + n + 1);//排序
    for (int i = 1; i <= n; i++) {
        if (m.count(sumCopy[i]) == 0) {
            m[sumCopy[i]] = id++;//用map判重并重新编号
        }
    }
    for (int i = 1; i <= n; i++)if (sum[i] > k)ans++;//首先把前缀和本身对应的合法子数列加上
    for (int i = 1; i <= n; i++) {
        int p = ID(sum[i] - k - 1, 1, n + 1);//找到第一个不大于sum[i]-k-1的前缀和编号，二分
        if (p != -1)ans += query(p);//存在满足条件的前缀和编号，用树状数组找数量
        add(m[sum[i]]);//把这个前缀和加入树状数组
    }
    cout << ans << endl;
    return 0;
}