线段树

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

今晚再打