可持久化线段树小结

学了可持久化线段树有一段时间了，一直没拿出时间来整理一下，刚好今天有空，就写一写。

可持久化的含义是对于每次修改操作都将产生一个新版本的线段树，并且旧版本的线段树仍然保留可以随时访问。

基于这个目的，我们可以采用类似动态开点的方法构建一颗线段树。

假设我们已经有了一个版本的线段树，我们要对这个线段树进行操作，我们首先复制前一颗线段树的根节点，然后在执行修改操作的时候，把所有途经的节点全部新建，其他节点保留。

一、包含单点修改，区间查询的可持久化线段树的实现

struct persist_segtree{
    struct Node{ //线段树的节点
        int lft,rgt; //左儿子指针和右儿子指针
        int num; //当前节点保存的值
    }segs[maxn];
    int rt[maxn]; //历史版本的线段树根节点指针
    int tot; //节点数目
    void init(){
        tot = 0;
        memset(segs,0,sizeof(segs));
    }
    inline int getnum(int rt){
       return rt?segs[rt].num:0;
    }
    void add(int &rt,int lft,int rgt,int pos,int num){ //修改操作
        int nrt = ++tot; //沿途的节点都要新建
        segs[nrt] = segs[rt]; //新建的节点是原节点的拷贝，然后再修改
        rt = nrt; 
        int mid = (lft + rgt)/2;
        if(lft == rgt){ //如果到达底部
            segs[rt].num += num;
            return ;
        }
        if(pos <= mid) //如果要修改的位置在左侧
            add(segs[rt].lft,lft,mid,pos,num);
	    else //如果要修改的位置在右侧
            add(segs[rt].rgt,mid+1,rgt,pos,num);
        segs[rt].num = getnum(segs[rt].lft) + getnum(segs[rt].rgt); //更新本节点的值
    }
    int query(int rt,int lft,int rgt,int beg,int end){
        if(!rt) return 0;
        if(beg <= lft && rgt <= end) return segs[rt].num;
        if(beg > rgt || end < lft) return 0;
        int mid = (lft + rgt)/2;
        return query(segs[rt].lft,lft,mid,beg,end) + query(segs[rt].rgt,mid+1,rgt,beg,end);
    }
}
                

1、查询，比如要查询第5个版本线段树的[3,199919991999]的区间和，那么查询语句可以这样写：

segtree.query(segtree.rt[5],1,1000000000,3,199919991999);
                

2、修改，比如在201720172017位置插入数值12345：

segtree.rt[t] = segtree.rt[t-1];
segtree.add(segtree.rt[t],1,1000000000,201720172017,12345);
                

二、区间修改

我也不知道为什么要把区间修改列在这里，其实区间修改就是lazy标记，和普通的线段树没有什么区别,有一点需要注意，就是在 标记下传 的时候，也要新建节点。
           

/*标记下传*/
	/*注意在标记下传的时候也要新开节点*/
	void down(int rt,int lft,int rgt){
        if(!segs[rt].lazy) return ;
        int mid = (lft + rgt)/2;
        segs[++tot] = segs[segs[rt].lft];
        segs[tot].num += segs[rt].lazy*(mid-lft+1);
        segs[tot].lazy += segs[rt].lazy;
        segs[rt].lft = tot;
        segs[++tot] = segs[segs[rt].rgt];
        segs[tot].num += segs[rt].lazy*(rgt-mid);
        segs[tot].lazy += segs[rt].lazy;
        segs[rt].rgt = tot;
        segs[rt].lazy = 0;
    }
    
                

查询和修改操作也要根据lazy标记做适当的修改

void add(int &rt,int lft,int rgt,int beg,int end,int num){
        int nrt = ++tot;
        segs[nrt] = segs[rt];
        rt = nrt;
        int mid = (lft + rgt)/2;
        if(beg <= lft && rgt <= end){
            segs[rt].num += (rgt-lft+1)*num;
            segs[rt].lazy += num;
            return ;
        }
        if(rgt < beg || end < lft) return ;
        down(rt,lft,rgt);
        if(lft <= end) add(segs[rt].lft,lft,mid,beg,end,num);
        if(rgt >= beg) add(segs[rt].rgt,mid+1,rgt,beg,end,num);
        segs[rt].num = getnum(segs[rt].lft) + getnum(segs[rt].rgt);
    }
    int query(int rt,int lft,int rgt,int beg,int end){
        if(!rt) return 0;
        if(beg <= lft && rgt <= end) return segs[rt].num;
        if(beg > rgt || end < lft) return 0;
        int mid = (lft + rgt)/2;
        down(rt,lft,rgt);
        return query(segs[rt].lft,lft,mid,beg,end) + query(segs[rt].rgt,mid+1,rgt,beg,end);
    }