模板

单点修改，查询区间和。

typedef long long ll;
const ll N=35*500000+10;
ll cnt=0;
struct SGT
{
	struct node{int lson,rson,data;}t[N];
	#define lson t[root].lson
	#define rson t[root].rson
	#define mid ((l+r)/2)
	ll update(ll root,ll l,ll r,ll pos,ll data)
	{
		if(root==0) root=++cnt;//开辟新节点
		if(l==r)
		{
			t[root].data+=data;
			return root;
		}
		if(pos<=mid) lson=update(lson,l,mid,pos,data);
		else rson=update(rson,mid+1,r,pos,data);
		t[root].data=t[lson].data+t[rson].data;
		return root;//返回地址
	}
	ll query(ll root,ll l,ll r,ll x,ll y)
	{
		ll ret=0;
		if(root==0) return 0;
		if(x<=l&&r<=y) return t[root].data;
		if(x<=mid) ret+=query(lson,l,mid,x,y);
		if(y>=mid+1) ret+=query(rson,mid+1,r,x,y);
		return ret;
	}
    ll build(ll root,ll l,ll r,ll a[])
	{
		root=++cnt;
		if(l==r){t[root].data=a[l];return root;}
		lson=build(lson,l,mid,a);
		rson=build(rson,mid+1,r,a);
        t[root].data=t[lson].data+t[rson].data;
		return root;
	}
}Tree;

例题

P1908 逆序对

题意

对于给定的一段正整数序列，逆序对就是序列中 $a_i>a_j$ 且 $i<j$ 的有序对。序列中有 $n$ 个数，求逆序对个数。

$n \leq 5 \times 10^5$ ， $a_i\le10^9$ 。

点击查看题解

题解

维护一棵权值动态开点线段树，其根节点管辖范围为 $1$ 至 $10^9$ 。

在 $10^9$ 的管理区间上，找到一点 $i$ ，不超过 $30$ 次，会经过不超过 $30$ 个节点，这些节点是我们实现对 $i$ 的操作所必须的，所以如果有对 $i$ 的操作，我们就动态开辟这些经过的节点。

按照定义，从 $1$ 至 $n$ ，先查询 $[a_i,10^9]$ 区间和（比 $a_i$ 大的数的个数），累加到 $ans$ ，再向线段树中插入数字。

附赠归并排序解法、树状数组解法。命名空间 _ActiveTree 为本做法。

代码

#include<bits/stdc++.h>
using namespace std;
namespace _sort
{
	const int N=500000+10;
	int n,a[N],b[N];
	long long ans=0;
	void Sort(int l,int r)
	{
		if(l>=r) return;
		int mid=(l+r)/2;
		int p1=l,p2=mid+1,pos=l;
		Sort(l,mid);Sort(mid+1,r);
		while(p1<=mid&&p2<=r)
		{
			if(a[p1]<=a[p2]) b[pos++]=a[p1++];
			else b[pos++]=a[p2++],ans+=mid-p1+1; 
		}
		while(p1<=mid) b[pos++]=a[p1++];
		while(p2<=r) b[pos++]=a[p2++];
		for(int i=l;i<=r;i++) a[i]=b[i];
	}
    void yzmain()
    {
    	scanf("%d",&n);
    	for(int i=1;i<=n;i++) scanf("%d",a+i);
    	Sort(1,n);
    	printf("%lld\n",ans);
        return;
    }
}
namespace _tree
{
	const int N=500000+10;
	struct data{int val,pos,rnk;}a[N];
	int n,t[N],p=0;
	long long ans=0;
	int lb(int x){return x&-x;}
	int query(int x){int ret=0;while(x>=1)ret+=t[x],x-=lb(x);return ret;}
	void update(int x,int y){while(x<=n)t[x]+=y,x+=lb(x);}
    void yzmain()
    {
    	scanf("%d",&n);
    	for(int i=1;i<=n;i++) scanf("%d",&a[i].val),a[i].pos=i;//Begin of 离散化 
    	sort(a+1,a+1+n,[](data a,data b)->bool{return a.val<b.val;});
    	for(int i=1;i<=n;i++)
    	{
    		if(a[i].val!=a[i-1].val) p++;//保证 val 相同的数，rnk 也相同。 
    		a[i].rnk=p;
		}
    	sort(a+1,a+1+n,[](data a,data b)->bool{return a.pos<b.pos;});//End of 离散化 
    	for(int i=n;i>=1;i--) ans+=query(a[i].rnk-1),update(a[i].rnk,1);
    	printf("%lld\n",ans);
        return;
    }
}
namespace _ActiveTree
{
	typedef long long ll;
	const ll N=35*500000+10,M=1000000000;
	ll cnt=0;
	struct SGT
	{
		struct node{int lson,rson,data;}t[N];
		#define lson t[root].lson
		#define rson t[root].rson
		#define mid ((l+r)/2)
		ll update(ll root,ll l,ll r,ll pos,ll data)
		{
			if(root==0) root=++cnt;
			if(l==r&&r==pos)
			{
				t[root].data+=data;
				return root;
			}
			if(pos<=mid) lson=update(lson,l,mid,pos,data);
			else rson=update(rson,mid+1,r,pos,data);
			t[root].data=t[lson].data+t[rson].data;
			return root;
		}
		ll query(ll root,ll l,ll r,ll x,ll y)
		{
			ll ret=0;
			if(root==0) return 0;
			if(x<=l&&r<=y) return t[root].data;
			if(x<=mid) ret+=query(lson,l,mid,x,y);
			if(y>=mid+1) ret+=query(rson,mid+1,r,x,y);
			return ret;
		}
	}Tree;
	ll n,a,ans=0,root;
	void yzmain()
	{
		scanf("%lld",&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%lld",&a);
			ans+=Tree.query(root,1,M,a+1,M);
			root=Tree.update(root,1,M,a,1);
		}
		printf("%lld\n",ans);
		return;
	}
}
int main()
{
    _ActiveTree::yzmain();
    return 0;
}

P3960 [NOIP2017 提高组] 列队

见文章 P3960 [NOIP2017 提高组] 列队。

P3919 【模板】可持久化线段树 1（可持久化数组）

题意

维护一个长度为 $N$ 的数组，支持如下几种操作：

在某个历史版本（ $v$ ）上修改某一个位置（ $loc$ ）上的值（ $a_{loc}$ ）为 $value$ 。
查询某个历史版本上的某一位置的值。

此外，每进行一次操作（对于操作 2，即为生成一个完全一样的版本，不作任何改动），就会生成一个新的版本。版本编号即为当前操作的编号（从 1 开始编号，版本 0 表示初始状态数组）。共进行 $M$ 次操作。

$1 \leq N, M \leq {10}^6$ ， $1 \leq {loc}_i \leq N$ ， $0 \leq v_i < i$ ， $-{10}^9 \leq a_i$ ， ${value}_i \leq {10}^9$ 。

点击查看题解

题解

维护 $M+1$ 棵动态开点线段树，按照题意进行即可。

一次单点修改，最多会让一个线段树上 $\log n$ 个节点发生改变，相邻历史版本其余的点可以共用。这样一次更改的时间复杂度是 $\log n$ ，所用空间也是 $\log n$ 。

新产生的节点中，只有一个儿子是新的，另一个儿子一定指向上一版本的儿子，从而实现共享。虽然每个节点可能出现多个父亲，但线段树中，我们都是找儿子节点，不会出现错误。

代码

#include<bits/stdc++.h>
using namespace std;
namespace _FullMarks
{
	typedef int ll;
	const ll N=1000000+10;
	ll n,m,a[N],root[N],cnt;
	struct SGT
	{
		struct node{int lson,rson,data;}t[N*30];
		#define lson t[root].lson
		#define rson t[root].rson
		#define mid ((l+r)/2)
		int clone(int pos)
		{
			t[++cnt]=t[pos];
			return cnt;
		}
		int build(int root,int l,int r,int a[])
		{
			root=++cnt;
			if(l==r){t[root].data=a[l];return root;}
			lson=build(lson,l,mid,a);
			rson=build(rson,mid+1,r,a);
			return root;
		}
		int update(int root,int l,int r,int pos,int data)
		{
			root=clone(root);//克隆一个点，现在它们暂时左右儿子公有
			if(l==r){t[root].data=data;return root;}
			if(pos<=mid) lson=update(lson,l,mid,pos,data);
			else rson=update(rson,mid+1,r,pos,data);
			return root;
		}
		int query(int root,int l,int r,int pos)
		{
			if(l==r) return t[root].data;
			if(pos<=mid) return query(lson,l,mid,pos);
			else return query(rson,mid+1,r,pos);
		}
	}Tree;
	void yzmain()
	{
		int t1,t2,t3,t4;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++) scanf("%d",a+i);
		root[0]=Tree.build(root[0],1,n,a);
		for(int i=1;i<=m;i++)
		{
			scanf("%d%d%d",&t1,&t2,&t3);
			if(t2==1)
			{
				scanf("%d",&t4);
				root[i]=Tree.update(root[t1],1,n,t3,t4);
			}
			else
			{
				printf("%d\n",Tree.query(root[t1],1,n,t3));
				root[i]=root[t1];
			}
		}
		return;
	}
}
int main()
{
	_FullMarks::yzmain();
	return 0;
}

本文作者：Yurchiu

本文链接：https://yz-hs.github.io/1e6c5a0361a9/

版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。

OI 树线段树动态开点线段树

最后更新：2021-07-09, 11:15:41

By Yurchiu.

随机文章回味旧文

博客信息

文章数目

158