树状数组又称二叉索引树(Binary Indexed Tree,BIT),是一种解决动态连续和查询问题的数据结构。
辅助数组 C:
Ci = Ai-lowbit(i)+1 + Ai-lowbit(i)+2 + ... + Ai
其中 lowbit(x) 代表 x的二进制表达式中最右边的1所对应的的值, 那么lowbit(x) = x & -x
即C[6] 代表 A[5] 和 A[6] 的和, C[4] 代表 A[1] + A[2] + A[3] + A[4]
那么如何求前缀和 Si 呢, 顺着结点i往左走, 边走边“往上爬”, 把沿途经过的 Ci 累加起来就可以了。
int sum(int x){ int ret = 0; while(x > 0){ ret += c[x]; x -= lowbit(x); } return ret; }
那么如果修改了一个 Ai, 需要更新 C数组 中的那些元素呢? 从 Ci 开始往右走, 边走边“往上爬”, 沿途修改结点对应的 Ci 即可。
void add(int x, int d){ while(x <= n){ c[x] += d; x += lowbit(x); } }
两个操作的时间复杂度仅为O(logn), 预处理的方法是先把 A 和 C 数组清空, 然后执行 n 次 add 操作, 总时间复杂度为O(nlogn)。
全部的代码如下:
#include <cstdio> #include <cstring> #include <iostream> using namespace std; const int maxn = 200; int a[maxn], c[maxn], n; int lowbit(int x){ return x & (-x); } void add(int x, int d){ while(x <= n){ c[x] += d; x += lowbit(x); } } int sum(int x){ int ret = 0; while(x > 0){ ret += c[x]; x -= lowbit(x); } return ret; } int main(){ scanf("%d", &n); for(int i=1; i<=n; i++){ scanf("%d", &a[i]); add(i, a[i]); } int l, r; scanf("%d%d", &l, r); printf("%d\n", sum(r)-sum(l-1)); return 0; }
图来自百度图片。
参考自《算法竞赛入门经典——训练指南》(刘汝佳)