动态开点线段树（改良）

· · 算法·理论

我永远喜欢线段树

注意到动态开点线段树每次最坏需要新开一条链，这是空间复杂度中 log 的来源，这其实也是比较浪费的，那么有没有办法每次只需要新开常数个点呢？这样就可以去掉空间上的 log 了。

假设我们有一棵无穷大的线段树，如下。（由于地方不够，只画了 [1,8] 的） 但是最开始我们一个点都不要。当我们插入一个数字如 2 时，我们选用点 [2,2] ，并使它作为根，即我们有了一棵值域为 [2,2] 的线段树。如图，标红的为选用的点。 之后可能会加入根值域外的数字，容易想到的是换一个值域更大的点作为根，而原来的根作为新根的子节点。不难发现，选用原来的根和新节点的 LCA 作为新的根是比较优的。

如插入点 [4,4] 时，选 [1,4] 作为新的根，[2,2] 和 [4,4] 分别作为根的左右节点。 之后插入节点时有两种可能的情况：该节点有对应方向的子节点和该节点没有对应方向的子节点。

没有对应方向的子节点时非常好办，直接作为该点的子节点就好了。如在下图中插入点 [7,7] 。 可以直接将 [7,7] 作为 [1,8] 的右节点，变为下图。 该节点有子节点的时候也有两种情况：该子节点值域完全包含新插入节点和该子节点不包含新插入节点。（区间修改时还可能出现新节点完全包含原子节点的情况，这个直接把新节点作为子节点，原来子节点作为新节点的子节点就好）

如果完全包含只需要像正常线段树一样往下递归就好，这里不多赘述。

我们考虑一下不被包含的情况，我们只需要像之前换根一样找这两个区间的 LCA 作为他们的父亲就好了。就像在上图中插入区间 [5,5]，只需要将区间 [5,8] 作为 [5,5] 和 [7,7] 的父亲, [1,8] 的右子节点就好了。

不难发现，这样每次最多只会开两个点， LCA 和自己。所以空间复杂度为插入次数 \mathcal{O}(m) ，时间是则是正常线段树的 \mathcal{O}(n\log V)， V 为值域，但是因为链的长度短了，所以常数比较小。

模板题可见这里

下面是模板题的实现代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=5e5+5;
const int N=1e9;
int n,m,root;
int lst;
struct segment_tree{
    #define ls(o) tr[o].ls
    #define rs(o) tr[o].rs
    #define l(o) tr[o].l
    #define r(o) tr[o].r
    #define mid(o) ((l(o)+r(o))>>1)
    struct node{
        int l,r,ls,rs,sum;
    }tr[maxn*2];int cnt;
    void pushup(int o){
        tr[o].sum=tr[ls(o)].sum+tr[rs(o)].sum;
    }
    int build(int l,int r){
        int lk=__lg(r-l+1),rk=__lg(r)+1;
        while(lk<rk){
            int m=(lk+rk)>>1;
            int len=1ll<<m;
            int rr=(r+len-1)/len*len,ll=rr-len+1;
            if(ll<=l)rk=m;
            else lk=m+1;
        }
        int len=1ll<<lk;
        int rr=(r+len-1)/len*len,ll=rr-len+1;
        tr[++cnt]={ll,rr,0,0,0};
        return cnt;
    }
    int merge(int x,int y){
        if(!x||!y)return x|y;
        if(l(x)>r(y)||r(x)<l(y)){
            int o=build(min(l(x),l(y)),max(r(x),r(y)));
            if(r(x)<=mid(o))ls(o)=x,rs(o)=y;
            else ls(o)=y,rs(o)=x;
            pushup(o);return o;
        }
        if(l(x)==l(y)&&r(x)==r(y)){
            if(l(x)==r(x)){
                tr[x].sum+=tr[y].sum;
                return x;
            }
            ls(x)=merge(ls(x),ls(y));
            rs(x)=merge(rs(x),rs(y));
            pushup(x);return x;
        }
        if(l(x)<=l(y)&&r(y)<=mid(x)){
            ls(x)=merge(ls(x),y);
            pushup(x);return x;
        }
        if(mid(x)<l(y)&&r(y)<=r(x)){
            rs(x)=merge(rs(x),y);
            pushup(x);return x;
        }
        if(l(y)<=l(x)&&r(x)<=mid(y)){
            ls(y)=merge(x,ls(y));
            pushup(y);return y;
        }
        if(mid(y)<l(x)&&r(x)<=r(y)){
            rs(y)=merge(x,rs(y));
            pushup(y);return y;
        }
    }
    void insert(int x,int y){
        tr[++cnt]={x,x,0,0,y};
        root=merge(root,cnt);
    }
    int query(int o,int x,int y){
        if(l(o)>y||r(o)<x)return 0;
        if(x<=l(o)&&r(o)<=y)return tr[o].sum;
        return query(ls(o),x,y)+query(rs(o),x,y);
    }
}tree;
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1,op,x,y;i<=m;i++){
        cin>>op>>x>>y;
        if(op==1){
            x=(x^lst)%n+1;y=(y^lst)%N;
            tree.insert(x,y);
        }else{
            x=(x^lst)%n+1;y=(y^lst)%n+1;if(x>y)swap(x,y);
            lst=tree.query(root,x,y);cout<<lst<<'\n';
        }
    }
    return 0;
}