树状数组 | 野生开发者

什么是树状数组？

就是用数组来模拟树形结构，可以解决大部分基于区间上的更新以及求和问题。树状数组可以解决的问题都可以用线段树解决，这两者的区别在哪里呢？树状数组修改和查询的复杂度都是 O(log n)，而且相比线段树系数要少很多，比传统数组要快，而且容易写。缺点是遇到复杂的区间问题还是不能解决，功能还是有限。树状数组多用于高效计算数列的前缀和。

核心思想

(1) 树状数组中的每个元素是原数组中的一个或多个连续元素的和；

(2) 在进行连续求和时，只需要将树状数组中某几个元素进行求和；

(3) 在对某一个元素进行修改时，只需要修改树状数组中某几个元素的和即可。

(4) 用 A 表示原始数组，C 表示树状数组，则：C[i] = A[i - 2^k + 1] + A[i - 2^k + 2] + … + A[i]；k为 i 的二进制中末尾连续的 0 的个数。

C[1] = A[1];

C[2] = A[1] + A[2];

C[3] = A[3];

C[4] = A[1] + A[2] + A[3] + A[4];

C[5] = A[5];

C[6] = A[5] + A[6];

C[7] = A[7];

C[8] = A[1] + A[2] + A[3] + A[4] + A[5] + A[6] + A[7] + A[8];

(5) C 中元素的后继(为此结点的父结点)：结点的后继是比它大、最近的且编号末尾连续 0 比它多的结点。

(6) C 中元素的前驱：结点的前驱为比它小、最近的且末尾连续 0 的个数比它多的结点。前驱主要用来计算连续和。

例如 i = 8(1000) 时候，k = 3，可自行验证。

这个怎么实现求和呢，比如我们要找前 7 项和，那么应该是 SUM = C[7] + C[6] + C[4]；

而根据上面的式子，容易的出 SUM[i] = C[i] + C[i - 2 ^ k1] + C[(i - 2 ^ k1) - 2 ^ k2] + …..；

其实树状数组就是一个二进制上面的应用。

现在新的问题来了：2 ^ k 该怎么求呢，不难得出 2 ^ k = i & (i ^ (i - 1))；但这个还是不好求出呀，于是就有：2 ^ k = i & (- i)；

为什么呢？

这里利用的负数的存储特性，负数是以补码存储的，对于整数运算 x & (-x) 有：

当 x 为 0 时，即 0 & 0，结果为 0；

当 x 为奇数时，最后一个比特位为 1，取反加 1 没有进位，故 x 和 - x 除最后一位外前面的位正好相反，按位与结果为 0。结果为 1。

当 x 为偶数，且为 2 的 m 次方时，x 的二进制表示中只有一位是 1（从右往左的第 m + 1 位），其右边有 m 位 0，故 x 取反加 1 后，从右到左第有 m 个 0，第 m + 1 位及其左边全是 1。这样，x & (- x) 得到的就是 x。

当 x 为偶数，却不为 2 的 m 次方的形式时，可以写作 x = y * (2 ^ k)。其中，y 的最低位为 1。实际上就是把 x 用一个奇数左移 k 位来表示。这时，x 的二进制表示最右边有 k 个 0，从右往左第 k + 1 位为 1。当对 x 取反时，最右边的 k 位 0 变成 1，第 k + 1 位变为 0；再加 1，最右边的 k 位就又变成了 0，第 k + 1位因为进位的关系变成了 1。左边的位因为没有进位，正好和 x 原来对应的位上的值相反。二者按位与，得到：第 k + 1 位上为 1，左边右边都为 0。结果为 2 ^ k。

总结一下：x & (-x)，当 x 为 0 时结果为 0；x 为奇数时，结果为 1；x 为偶数时，结果为 x 中 2 的最大次方的因子。

而且这个有一个专门的称呼，叫做 lowbit，即取 2 ^ k。

基本操作

1.预备函数 lowbit(int)

树状数组最基本的操作就是找到前驱和后继。lowbit 函数返回将参数转化为二进制后最后一个 1 所在的位置转化为十进制后的值。例如，34 转化二进制为 100010，最后一个 1 在第二位，所以返回 10，即 2 。

1
2
3

int lowbit(int k){
    return k & (-k);
}

2.修改原始数据某一元素的值

将 a[k] 的值增加 v ，需要把 e[k] 以及其后继结点的值全部加 k ，一直到 LEN (数组最大长度)。

#define LEN 100
int e[LEN];
void add(int k, int v){
    while(k < LEN){
        e[k] += v;
        k += lowbit(k);
    }
}

3.求原始数据前 k 项的和

只需要把 e[k] 以及其前驱结点的值累加即可。

int sum(int k){
    int re = 0;
    while(k > 0){
        re += e[k];
        k -= lowbit(k);
    }
    return re;
}

代码实现

模板题

#include <iostream>
#include <string>
#include <cstring>
using namespace std;

int n;
int a[50005],c[50005]; //对应原数组和树状数组

int lowbit(int x){
    return x & (-x);
}

void update(int i,int k){  //在i位置加上k
    while(i <= n){
        c[i] += k;
        i += lowbit(i);
    }
}

int getsum(int i){  //求A[1 - i]的和
    int res = 0;
    while(i > 0){
        res += c[i];
        i -= lowbit(i);
    }
    return res;
}

int main(){
    int t;
    cin >> t;
    for(int tot = 1; tot <= t; tot++){
        cout << "Case " << tot << ":" << endl;
        memset(a, 0, sizeof a);
        memset(c, 0, sizeof c);
        cin >> n;
        for(int i = 1; i <= n; i++){
            cin >> a[i];
            update(i, a[i]);  //输入初值的时候，也相当于更新了值
        }

        string s;
        int x, y;
        while(cin >> s && s[0] != 'E'){
            cin >> x >> y;
            if(s[0] == 'Q'){  //求和操作
                int sum = getsum(y) - getsum(x-1);  //x-y区间和也就等于1-y区间和减去1-(x-1)区间和
                cout << sum << endl;
            }
            else if(s[0] == 'A'){
                update(x, y);
            }
            else if(s[0] == 'S'){
                update(x, -y);  //减去操作，即为加上相反数
            }
        }

    }
    return 0;
}

树状数组的几种变式(区间更新，区间查询)

1.单点更新、单点查询

2.单点更新、区间查询

3.区间更新、单点查询

这就是第一个问题，如果题目是要把 x - y 区间内的所有值全部加上 k 或者减去 k ，然后查询操作是问某个点的值。如果是像上面的树状数组来说，就必须把 x - y 区间内每个值都更新，这样的复杂度肯定是不行的，这个时候，就不能再用数据的值建树了，这里我们引入差分，利用差分建树。

假设我们规定 A[0] = 0，则有 A[i] = ΣD[j] (D[j] = A[j] - A[j - 1])。那么当某个区间 [x, y] 值改变了，区间内的差值是不变的，只有 D[x] 和 D[y + 1] 的值发生改变。

int n;
int a[50005] = {0};
int sum1[50005];  //(D[1] + D[2] + ... + D[n])
int sum2[50005];  //(1*D[1] + 2*D[2] + ... + n*D[n])

int lowbit(int x){
    return x & (- x);
}

void update(int i, int k){
    int x = i;  //因为x不变，所以得先保存i值
    while(i <= n){
        sum1[i] += k;
        sum2[i] += k * (x - 1);
        i += lowbit(i);
    }
}

int getsum(int i){  //求前缀和
    int res = 0, x = i;
    while(i > 0){
        res += x * sum1[i] - sum2[i];
        i -= lowbit(i);
    }
    return res;
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        update(i, a[i] - a[i - 1]);  //输入初值的时候，也相当于更新了值
    }

    //[x,y]区间内加上k
    update(x, k);  //A[x] - A[x-1]增加k
    update(y + 1, - k);  //A[y+1] - A[y]减少k

    //求[x,y]区间和
    int sum = getsum(y) - getsum(x - 1);

    return 0;
}