created by Dejavu*
[完结]
-
简介
树状数组(Binary Indexed Tree(BIT), Fenwick Tree)是一个查询和修改复杂度都为log(n)的数据结构。主要用于查询任意两位之间的所有元素之和，但是每次只能修改一个元素的值；经过简单修改可以在log(n)的复杂度下进行范围修改，但是这时只能查询其中一个元素的值。
树状数组十分容易实现，代码量小，时间复杂度低，并且经过数学处理后也可以实现成段更新。线段树也可以做到和树状数组一样的效果，但是代码要复杂得多。不过要注意，一般情况下树状数组能解决的问题线段树都能解决，反之有些线段树能解决的问题树状数组却不行。
BIT的部分代码int lowbit(int t) {return t&-t;} void add(int p,int v) {for(;p<=n;bt[p]+=v,p+=lowbit(p));} int sum(int p) { int s(0); for(;p>0;s+=bt[p],p-=lowbit(p)); return s; }这里的lowbit作用是取最低位的1，p每次加上lowbit，p都是在加2的整数倍(除1外)以此来更新与p点数据相关的节点数据，从而快速构建起一棵树，所以n以下最大的lowbit数将作为顶节点，而超过最大的lowbit数时，树将与最大lowbit数建立的树分离，使得计算sum时只能采用分布计算做差来取得结果
计算区间[5,9]的和时，sum_out = sum(9)-sum(5-1)
计算过程，例如当idx = 13; sum初始 = 0:
| number | binary | after lowbit() |
|---|---|---|
| 1 | 0001 | 0001 |
| 2 | 0010 | 0010 |
| 3 | 0011 | 0001 |
| 4 | 0100 | 0100 |
| 5 | 0101 | 0001 |
| 6 | 0110 | 0010 |
| ... |
| iteration | idx | position of the last digit | idx & -idx | sum |
|---|---|---|---|---|
| 1 | 13 = 1101 | 0 | 1 (2 ^0) | 3 |
| 2 | 12 = 1100 | 2 | 4 (2 ^2) | 14 |
| 3 | 8 = 1000 | 3 | 8 (2 ^3) | 26 |
| 4 | 0 = 0 | — | — | — |
-
代码
#include <iostream> using namespace std; #define MAXN 1000 int n; int bt[MAXN] = {0}; int lowbit(int t) {return t&-t;} void add(int p,int v) {for(;p<=n;bt[p]+=v,p+=lowbit(p));} int sum(int p) { int s(0); for(;p>0;s+=bt[p],p-=lowbit(p)); return s; } int main() { cin >> n; for(int i=1;i<=n;i++) { int tmp;cin>>tmp; add(i,tmp); } char cmd; int in1,in2; while(cin>>cmd,cmd!='E') { cin >> in1 >> in2; if(cmd == 'Q') cout << sum(in2)-sum(in1-1) <<endl; else if(cmd == 'A') add(in1,in2); } }
