可持久化线段树

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
///sr函数支持单点修改
///red函数支持区间查询
///单点操作可以写成非递归while形式，加快速度
struct btree{
    btree *o[2];
    int cnt;
    LL d;
}tbt[maxn*50],tnull; int tpo;
btree *newnode()
{
    btree *p=&tbt[tpo++];
    *p=tnull;
    return p;
}
btree *sr(btree *t,int l,int r,int x,int v,int d)
{
    btree *p=newnode();
    if (t) *p=*t;
    p->cnt+=v; p->d+=d;
    if (l==r) return p;
    int mid=l+r>>1;
    if (x<=mid) p->o[0]=sr(p->o[0],l,mid,x,v,d);
    else        p->o[1]=sr(p->o[1],mid+1,r,x,v,d);
    return p;
}
int red(btree *t,int l,int r,int ll,int rr)
{
    if (!t) return 0;
    if (ll<=l&&r<=rr) return t->cnt;
    int mid=l+r>>1,ret=0;
    if (ll<=mid) ret+=red(t->o[0],l,mid,ll,rr);
    if (rr>mid)  ret+=red(t->o[1],mid+1,r,ll,rr);
    return ret;
}
}}}

///sr函数支持单点修改
///red函数支持区间查询
///单点操作可以写成非递归while形式，加快速度
struct btree{
    btree *o[2];
    int cnt;
    LL d;
}tbt[maxn*50],tnull; int tpo;
btree *newnode()
{
    btree *p=&tbt[tpo++];
    *p=tnull;
    return p;
}
btree *sr(btree *t,int l,int r,int x,int v,int d)
{
    btree *p=newnode();
    if (t) *p=*t;
    p->cnt+=v; p->d+=d;
    if (l==r) return p;
    int mid=l+r>>1;
    if (x<=mid) p->o[0]=sr(p->o[0],l,mid,x,v,d);
    else        p->o[1]=sr(p->o[1],mid+1,r,x,v,d);
    return p;
}
int red(btree *t,int l,int r,int ll,int rr)
{
    if (!t) return 0;
    if (ll<=l&&r<=rr) return t->cnt;
    int mid=l+r>>1,ret=0;
    if (ll<=mid) ret+=red(t->o[0],l,mid,ll,rr);
    if (rr>mid)  ret+=red(t->o[1],mid+1,r,ll,rr);
    return ret;
}