概念:
树状数组是一个查询和修改复杂度都为log(n)的数据结构
结构:
c【8】=a1+a2+a3。。。。a8。
即:C[i]表示A[i-2^k+1]到A[i]的和。
8的二进制1000,三个0,k就等于3.
那么用计算机怎么求K呢?
可以用计算机的特性:
int lowbit(int x) { return x&(-x); }
输入x,输出2^k。比如说输入8,输出8。
求s【n】(a1+a2+....an)
int sum(int s) { int ss; ss=0; while(s>0) { ss+=c[s]; s=s-lowbit(s); } return ss; }
返回的ss即为所求的值。
改变a【x】的值。
void add(int x,int num) { for(;x<len;x+=lowbit(x)) { c[x]+=num; } }
num为变化的值