线段树（区间修改树）

2020-12-08
所谓线段树，是指对于一个int[] arr，用O(logn)实现以下方法：
add(l,r,v):l到r增加v
update(l,r,v):l到r更新为v
getSum(l,r):获取l到r所有和
思路：
补成满二叉树，用数组存储
左孩子2*i
右孩子2*1+1
代码如下：
//ps:执行操作时，后三位永远不变
public static class SegmentTree{
    private int MAXN;
    private int[] arr;//复制原数组，起始位置为1
    private int[] sum;//模拟线段树维护区间和
    private int[] lazy;//懒惰标记，懒增加信息
    private int[] change;//更新值
    private boolean[] update;//懒惰更新标记
    public SegmentTree(int[] origin){
        MAXN=origin.length+1;
        arr=new int[MAXN];
        for(int i=1;i<MAXN;i++){
            arr[i]=origin[i-1];
        }
        sum=new int[MAXN<<2];//相当于*4，即使是n=5，需要的位置也无非2^4=16，所以*4完全够
        lazy=new int[MAXN<<2];
        change=new int[MAXN<<2];
        update=new boolean[MAXN<<2];
        //build(1,MAXN-1,1);
    }
    public void build(int l,int r,int rt){//实际使用时需要build
        if(l==r){
            sum[rt]=arr[l];
            return;
        }
        int mid=(l+r)>>1;
        //递归加和
        build(l,mid,rt<<1);
        build(mid+1,r,rt<<1|1);
        pushUp(rt);
    }
    //懒增加，范围涵盖不向下传
    public void add(int L,int R,int C,int l,int r,int rt){//LR为增加区间，C为加数，lr为当前区间，rt为数组位置
        //任务覆盖，懒更新
        if(L<=l&&r<=R){
            sum[rt]+=C*(r-l+1);
            lazy[rt]+=C;
            //这里add方法不能覆盖update方法
            return;
        }
        //任务未覆盖
        int mid=(l+r)>>1;
        //下发之前所有积攒的懒惰任务!!所有任务都要在未覆盖时执行
        pushDown(rt,mid-l+1,r-mid);
        if(L<=mid){//左孩子接到懒任务
            add(L,R,C,l,mid,rt<<1);
        }if(R>mid){//右孩子接到懒任务
            add(L,R,C,mid+1,r,rt<<1|1);
        }
        pushUp(rt);//汇总信息
    }
    public void update(int L,int R,int C,int l,int r,int rt){
        if(L<=l&&r<=R){
            update[rt]=true;
            change[rt]=C;
            sum[rt]=C*(r-l+1);
            lazy[rt]=0;
            return;
        }
        //懒信息下发
        int mid=(l+r)>>1;
        pushDown(rt,mid-l+1,r-mid);
        if(L<=mid){
            update(L,R,C,l,mid,rt<<1);
        }if(R>mid){
            update(L,R,C,mid+1,r,rt<<1|1);
        }
        pushUp(rt);
    }
    public long query(int L,int R,int l,int r,int rt){
        if(L<=l&&r<=R){
            return sum[rt];
        }
        int mid=(l+r)>>1;
        pushDown(rt,mid-l+1,r-mid);
        long ans=0;
        if(L<=mid){
            ans+=query(L,R,l,mid,rt<<1);
        }if(R>mid){
            ans+=query(L,R,mid+1,r,rt<<1|1);
        }
        return ans;
    }
    //sum信息上传
    private void pushUp(int rt){
        sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    }
    //懒信息下传,先更新再增加，以免增加被覆盖!!!
    private void pushDown(int rt,int ln,int rn){//ln表示左孩子数目
        if(update[rt]){//懒更新的分发策略
            update[rt<<1]=true;
            update[rt<<1|1]=true;
            
            change[rt<<1]=change[rt];
            change[rt<<1|1]=change[rt];
            
            lazy[rt<<1]=0;
            lazy[rt<<1|1]=0;
            
            sum[rt<<1]=change[rt]*ln;
            sum[rt<<1|1]=change[rt]*rn;
            
            update[rt]=false;
        }
        if(lazy[rt]!=0){//父结点懒信息不为0
            lazy[rt<<1]+=lazy[rt];
            sum[rt<<1]+=lazy[rt]*ln;
            lazy[rt<<1|1]+=lazy[rt];
            lazy[rt<<1|1]+=lazy[rt]*rn;
            lazy[rt]=0;
        }
    }
}