线段树

线段树

主要由五个操作：
pushup()：由子节点算父节点的信息。例如计算当前区间的总和，父亲节点等于左右两个结点的区间之和
pushdown()：由父节点传递给子节点的信息。也被称为懒标记。
build():将一段区间初始化为线段树
modify():修改某一个点或者某一个区间
query():查询某一段区间的信息

一般使用一维数组存整棵树。从编号为1开始存储
编号为x的父亲结点x/2,左儿子：2*x,右儿子：2*x+1
其中有n个叶子节点。最坏的情况下会有4*n-1个点，所以一般的情况下会开4n个结点

void build(int u,int l,int r){//当前结点编号，左右孩子编号 
　　tr[u].l=l,tr[u].r=r;
　　if(l==r) {
　　//如果需要在叶子结点存储来自输入的信息，可以直接在这里cin>>
　　return;
　　}
int mid=l+r>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(u);
}

查询分为2种情况，需要查询的区间[L,R],当前访问的线段树区间[l,r]
1:L<=l,R>=r,直接返回当前区间的信息就可以了，不用继续向下搜索了
2：只有一部分存在交集。

单点修改不需要懒标记

懒标记：pushdown()
扫描线法

懒标记：加上懒标记可以完成区间修改的操作。跟区间查询的操作类似。修改一个区间，当遇到一个完成的区间的时候，就标记这个区间，并返回，不继续向下继续修改
给以当前结点为根的子树中的每一个结点都包含这个懒标记，/*但是当前区间结点并不包括*/

一般而言，pushup()需要放在build()和modify()的后面。
pushdown()放在modify()和query()的前面

除了build()之外，其他的函数的区间直接向下传递l,r不用传递mid

void pushup(int u){
    tr[u].v=max(tr[u<<1].v,tr[u<<1|1].v);
}

int query(int u,int l,int r){
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u].v;
    int v=0;
    int mid=tr[u].l+tr[u].r>>1;
    if(l<=mid) v=query(u<<1,l,r);
    if(r>mid) v=max(v,query(u<<1|1,l,r));
    return v; 
}

void modify(int u,int x,int d){ //这是最简单的一个modify，因为这是单点修改 
    if(tr[u].l==x&&tr[u].r==x) {
        tr[u].v=d;
        return ;
    }
    else {
        int mid=tr[u].l+tr[u].r>>1;
        if(x<=mid) modify(u<<1,x,d);
        if(x>mid) modify(u<<1|1,x,d);
        pushup(u);
    }
}

void modify(int u,int x,ll d){//区间修改
    if(tr[u].l==x&&tr[u].r==x){
        tr[u].gc+=d;
        return ;
    }
    int mid=tr[u].l+tr[u].r>>1;
    if(x<=mid) modify(u<<1,x,d);
    if(x>mid) modify(u<<1|1,x,d);
    pushup(u);
    return ;
}

void pushdown(int u){
    if(tr[u].add!=0){
        tr[u<<1].sum+=(tr[u<<1].r-tr[u<<1].l+1)*tr[u].add;
        tr[u<<1].add+=tr[u].add;
        tr[u<<1|1].sum+=(tr[u<<1|1].r-tr[u<<1|1].l+1)*tr[u].add;
        tr[u<<1|1].add+=tr[u].add;
        tr[u].add=0;
    }
}

写于：2020/8/29  22:40