树状数组 - Tom Smith's

BYvoid神犇曾经说过。

树状数组是一个优美小巧的数据结构

它没有像其他数据结构那样复杂，在很多时候可以代替线段树，它仅通过简单的几个函数，不需要任何其他的空间，就成功的把求前序和的时间复杂度降到了$O(\log_2 n)$，当然代价就是插入的时间复杂度也变成了$O(\log_2 n)$，不过为了能够快速的求前序和，这是在所难免的。在树状数组中，一个元素所代表并不只有自己，比如a[15]，因为15的二进制是00001111，所以这个a[00001111] = a[00001110] + a[00001100] + a[00001000]；即a[15] = a[14] + a[12] + a[8]；

树状数组主要的三个操作

1
2
3
4


int lowbit(int a){          //取出这个数二进制中的最后一个1
    return a & (-a);
}

修改

1
2
3
4
5
6
7


void modify(int n, int c){  //a[n]=c
    while(n <= N){
        a[n] += c;
        n += lowbit(n);
    }
}

前缀和

1
2
3
4
5
6
7
8
9


int sum(int n){     
    int r = 0;
    while(n){
        r += a[n];
        n -= lowbit(n);
    }
    return r;
}

假如想要求[a, b]区间的和可以用sum(b) - sum(a)实现

Table of Contents