线段树

· · 个人记录

线段树是一种基于分治想法的二叉树。

用来维护区间各种值(如最大，区间和等)。

build 建树的写法是如果没到叶子结点( l≠r 时)开始分裂

int m=tr[p].l+tr[p].r>>1;

接着找到子节点赋值

updata 用于更改，原理近似于 build ，如果是单个改就只找到 l=r 时， 如果区间就得加入懒标记。

求结果的因题而异，无非就是找到返回，没找到裂开。

而懒标记的出现是在区间查询中，如果每次改时都下传未免太慢，我们可以搞一个懒标记变量以便下次更改。

而下传我们可以写个函数 powdown ：

#define lc p*2
#define rc p*2+1
void pd(int p){//p为当前值
    if(tr[p].add){
    tr[lc].sum+=tr[p].add*(tr[lc].r-tr[lc].l+1);    
    tr[rc].sum+=tr[p].add*(tr[rc].r-tr[rc].l+1);
    tr[lc].add+=tr[p].add;  
    tr[rc].add+=tr[p].add;
    tr[p].add=0;    
    }
}

然后每次查询如果有就下传即可。

训练可以参考P3372|P3374