树状数组

 

 

lowbit(i)=i & -i

c_i=i-lowbit(i)+1 ~ i

c_{1 2 3 4 5 6 7 8...}

for(1~i) sum+=c_i

区间加值：i+lowbit(i)

修改单点

 

 

 

while(i!=0){    sum+=c[i];}

 

区间修改

在两个端点各加一个标记

 

区间查询

求1~i

前缀和 sum_i

sum_i

线段树

适合具备结合律的运算（sum，xor，max，min……）

像归并排序一样，把所有数据反复切一半

那么叶子节点即为原数的自身区间    exam：[i,i]

按照BFS的顺序将这棵树编号（外层为层数，内层为同意层的序号）

最后一层节点可能不是连续的，直接空出来即可。

可以发现，每个非叶子节点的左儿子的编号是其两倍，右儿子的编号是其两倍加一

保存线段树的数组（struct）长度不能小于4*N

void build(int now,int l,int r)

1. 更新l,r
2. 判断是否为叶子节点（l==r）
3. int mid=(l+r)>>2//卡常省时
4. build左区间&&右区间
5. 回溯后（不用返回值）将数据代入递推式

递推式：（以max为例）

dat[l,r]=max(dat[l,mid],dat[mid,r])

建立线段树以后，每个节点上的信息就为其对应区间的最大值