1.建树，递归建树即可，o(n)算法的是什么鬼...；
void build(int l,int r ,int k) l是左边界，r是右边界，k是线段树中的下标
{
int m;
if(l==r){
t[k].l=l;
t[k].r=r;
t[k].n=0; n是元素的总和，类似的也可以维护别的附加信息；
return ; 递归的边界；
}
m=(l+r)/2;
t[k].l=l;
t[k].r=r;
t[k].n=0;
build(l,m,2*k);
build(m+1,r,2*k+1)
}
然后就是插入或者说更新；插入和更新用同一个函数即可；
感觉好像代码都是相似的，都是要是到达叶节点的时候就搞他，要是没有的话就看看要在左边搞还是在右边搞，要不然就两边一起搞，插入更新的话就要在最后再搞一下然后好像就没有了qwq
今晚再打
原文：http://www.cnblogs.com/20003238wzc--/p/4785274.html