关于我口胡出来一种可以维护带修改的前缀和（max，异或等）的数据结构这件事

常规
1

本文同步到CSDN ，洛谷灌水区

这种数据结构能将原本的前缀和 O(1) 查询和 O(n) 修改的缺陷平衡至 O(logn*loglogn) 修改与查询。而且，如果您嫌麻烦的话，也可以实现一个 O(log^2n) 查询， O(logn) 修改前缀和的数据结构。缺点是空间复杂度会变大。

这种数据结构，我称它为高效前缀和树。当然，如果您爱好珂学的话，我bb出来另一个名字：威廉树

如果我们要维护一个序列 A 的前缀和，我们可以直接用一个 sum 数组保存。但是这种方法简陋且不具有美感。

我们可以以整个序列上的元素建造一棵二叉树。请注意，它不同于线段树和树状数组，它仅仅是将 $A_1…A_1$作为根节点， A_2...A_3 从左到右作为第一层， A_4...A_7 从左到右作为第二层，以此类推。它是一棵完全二叉树。

二叉树上的点有点权，边有边权。边权不会改动。一个点 A_x 到根节点路径上所有边的边权和和点权和就是 A_x 的初始前缀和。

先不讨论点权，它初始是 0 。

边权具体是多少？ 还是以 x 为例子， A_x 到它的父亲 A_f 的边权就是区间 [f+1,x] 的和。边权均可以用 O(n) 的预处理求。

很显然，“一个点 A_x 到根节点路径上所有边的边权和就是 A_x 的初始前缀和” 这句话是正确的。我们仅仅是将一个前缀和分成了 logn 段。

假如我们要修改一个值（例如加减 $k$），那么此时将会有一些与其相对应的边权需要改动。但是由于这些边都连向同一或同二层，我们显然有一种更加巧妙的方法修改：

我们将两层上需要修改的入边分别考虑。每一层上的点都是连续的。于是将这些点分为 logn 段，每段长度都可以用 2^p 表示， p 为自然数。可以 O(1) 求出每一段的 LCA ，我们将这些 LCA 的结果增加深度数组上的点权。

例如，我们修改一个点 A_7 时，分出来两层 [7,7] 与 [8,13] 、假设我们要处理 [8,13] 的，我们又可以分为两段 [8,11] 与 [12,13] 。此时只需要修改 A_2 与 A_6 的点权就行了。

但是这样有一个问题：我们要查询 [1,4] 的前缀和，仍然会遍历到 A_2 。而 [7,13] 是不包括 [1,4] 的！

所以对于每一个点，开辟一个深度数组的空间，用树状数组维护 或者暴力维护 。我们修改点权时，记录使它修改的那一层的深度，并在深度数组上记录点权的修改情况。当我们遍历到修改过的点时，只需要看起始深度是否比修改深度大就行了。

好了！你可能觉得这并没有什么用。但其实 loglogn 的时间复杂度极小。且它可以用同样的方法维护带修改的前缀max，前缀异或，以及一些奇奇怪怪的前缀。

代码可行，已经被我写出来了。 等我先过一下线段树模板再放在讨论区

1 个赞
2 
#include <bits/stdc++.h>
using namespace std;

struct node{
	int lson,rson,fanum;
	int pointnum[20];
};

struct ti{
	int now,father,dept;
};

int a[100000];
node willam_tree[100000];
int lblock[1000],rblock[1000],tot=0,cnt=0;
int sum[100000],deep[100000],lg[100000],allsums[1000];
int fa[100000][30];
int n,q,numt=1,mxn2=1,cntn2=0,maxdeep=-1;

void build(int nw,int f,int dep){
	queue <ti>q;
	q.push((ti){nw,f,dep});
	while(!q.empty()){
		ti n6=q.front();
		q.pop();
		nw=n6.now;
		f=n6.father;
		dep=n6.dept;
		if(nw!=0){
			willam_tree[nw].fanum=sum[nw]+(allsums[dep-1]-sum[f]);
		}
		willam_tree[nw].lson=++cnt;
		willam_tree[nw].rson=++cnt;
		if(willam_tree[nw].rson<n){
			q.push((ti){willam_tree[nw].lson,nw,dep+1});
			q.push((ti){willam_tree[nw].rson,nw,dep+1});
		}else if(willam_tree[nw].lson<n){
			q.push((ti){willam_tree[nw].lson,nw,dep+1});
		}
	}
}

void dfs(int now,int fth)
{
  	fa[now][0]=fth;
  	if(fth==-1){
  		deep[now]=0;
	}else{
  		deep[now]=deep[fth]+1;
	}
  	for(int i=1; i<=lg[deep[now]]; i++)
  	{
    	fa[now][i]=fa[fa[now][i-1]][i-1];
  	}
  	if(willam_tree[now].lson<n){
    	dfs(willam_tree[now].lson,now);
	}
  	if(willam_tree[now].rson<n){
    	dfs(willam_tree[now].rson,now);
	}
	maxdeep=max(maxdeep,deep[now]+1);
}

int ask(int x,int firsts){
	if(x==-1){
		return -a[0];
	}
	int anss=0;
	for(int i=1;i<=firsts;i++){
		if(willam_tree[x].pointnum[i]!=0){
			anss+=willam_tree[x].pointnum[i];
		}
	}
	if(x==0){
		return anss;
	}
	return ask(fa[x][0],firsts)+anss+willam_tree[x].fanum;
}

void update(int p,int zz){
	int lx=p,rx=rblock[deep[p]+1],ly=lblock[deep[willam_tree[p-1].rson]+1]==0 ? mxn2/2-1 : lblock[deep[willam_tree[p-1].rson]+1],ry=min(n-1,willam_tree[p-1].rson);
	if(deep[p]+1==deep[willam_tree[p-1].rson]+1){
		willam_tree[0].pointnum[deep[p]+1]+=zz;
		return;
	}
	if(deep[p]+1==maxdeep){
		ly=ry+1;
	}
	for(int z=mxn2,r=cntn2;z>=1 && lx<=rx;z/=2,r--){
		if(rx-z>=lx-1){
			if(r==0){
				willam_tree[rx-z+1].pointnum[deep[p]+1]+=zz;
			}else{
				willam_tree[fa[rx-z+1][r-1]].pointnum[deep[p]+1]+=zz;
			}
			rx-=z;
		}
	}
	for(int z=mxn2,r=cntn2;z>=1 && ly<=ry;z/=2,r--){
		if(ly+z<=ry+1){
			if(r==0){
				willam_tree[ly].pointnum[deep[willam_tree[p-1].rson]+1]+=zz;
			}else{
				willam_tree[fa[ly][r-1]].pointnum[deep[willam_tree[p-1].rson]+1]+=zz;
			}
			ly+=z;
		}
	}
}

int main(){
	lblock[0]=0;
	cin >> n >> q;
	while(mxn2<n){
		mxn2*=2;
		cntn2++;
	}
	for(int i=0;i<n;i++){
		cin >> a[i];
		if(numt==i+1){
			rblock[tot]=i-1;
			lblock[++tot]=i;
			numt*=2;
		}
		if(i==n-1){
			rblock[tot]=i;
		}
	}
	sum[1]=a[0];
	for(int i=2;i<=tot;i++){
		sum[lblock[i]]=a[lblock[i]];
		for(int j=lblock[i]+1;j<=rblock[i];j++){
			sum[j]=a[j]+sum[j-1];
			if(j==rblock[i]){
				allsums[i]=sum[j];
			}
		}
	}
	build(0,-1,1);
	for(int i=1; i<=n; i++)
	{
	    lg[i]=lg[i-1]+(1<<lg[i-1]==i);
	}
	dfs(0,-1);
	while(q--){
		int opt,x,y;
		cin >> opt >> x >> y;
		if(opt==1){
			x--;
			update(x,y);
		}else{
			x--;
			y--;
			int deptx=deep[x-1]+1;
			int depty=deep[y]+1;
			cout << (ask(y,depty)+a[0])-(ask(x-1,deptx)+a[0]) << endl;
		}
	}
	return 0;
}
1 个赞
3

没有人指出错误吗？顶

4

update1：加入树状数组维护，另外修复几个bug

bug：当修改的 A_x 在树的最后一层时，分段时会出现问题，因为树的最后一层不一定满。考虑建立虚点，将其补全成一棵满二叉树。

#include <bits/stdc++.h>
using namespace std;

struct node{
	int lson,rson,fanum;
	int pointnum[20][6];
};

struct ti{
	int now,father,dept;
};

int a[100000];
node willam_tree[100000];
int lblock[1000],rblock[1000],tot=0,cnt=0;
int sum[100000],deep[100000],lg[100000],allsums[1000];
int fa[100000][30];
int n,q,numt=1,mxn2=1,cntn2=0,maxdeep=-1;

void build(int nw,int f,int dep){
	queue <ti>q;
	q.push((ti){nw,f,dep});
	while(!q.empty()){
		ti n6=q.front();
		q.pop();
		nw=n6.now;
		f=n6.father;
		dep=n6.dept;
		if(nw>=n){
			willam_tree[nw].fanum=0;
		}else if(nw!=0){
			willam_tree[nw].fanum=sum[nw]+(allsums[dep-1]-sum[f]);
		}
		willam_tree[nw].lson=++cnt;
		willam_tree[nw].rson=++cnt;
		if(willam_tree[nw].rson<mxn2){
			q.push((ti){willam_tree[nw].lson,nw,dep+1});
			q.push((ti){willam_tree[nw].rson,nw,dep+1});
		}else if(willam_tree[nw].lson<mxn2){
			q.push((ti){willam_tree[nw].lson,nw,dep+1});
		}
	}
}

void dfs(int now,int fth)
{
  	fa[now][0]=fth;
  	if(fth==-1){
  		deep[now]=0;
	}else{
  		deep[now]=deep[fth]+1;
	}
  	for(int i=1; i<=lg[deep[now]]; i++)
  	{
    	fa[now][i]=fa[fa[now][i-1]][i-1];
  	}
  	if(willam_tree[now].lson<mxn2){
    	dfs(willam_tree[now].lson,now);
	}
  	if(willam_tree[now].rson<mxn2){
    	dfs(willam_tree[now].rson,now);
	}
	maxdeep=max(maxdeep,deep[now]+1);
}

int lglg[10]={1,2,4,8,16,32,64,128,256,512};

void add(int x,int y,int w){
	y--;
	for(int i=0;i<6;i++){
		willam_tree[x].pointnum[y+1][i]+=w;
		y/=2;
	}
}

int de(int x,int l,int r){
	int anss2=0;
	for(int i=5;i>=0 && l<=r;i--){
		if(l+lglg[i]<=r+1){
			anss2+=willam_tree[x].pointnum[l][i];
			l+=lglg[i];
		}
	}
	return anss2;
}

int ask(int x,int firsts){
	if(x==-1){
		return -a[0];
	}
	int anss=de(x,1,firsts);
	if(x==0){
		return anss;
	}
	return ask(fa[x][0],firsts)+anss+willam_tree[x].fanum;
}

void update(int p,int zz){
	int lx=p,rx=rblock[deep[p]+1],ly=lblock[deep[willam_tree[p-1].rson]+1]==0 ? mxn2/2-1 : lblock[deep[willam_tree[p-1].rson]+1],ry=min(n-1,willam_tree[p-1].rson);
	if(deep[p]+1==deep[willam_tree[p-1].rson]+1){
		add(0,deep[p]+1,zz);
		return;
	}
	if(deep[p]+1==maxdeep){
		ly=ry+1;
	}
	if(rblock[deep[p]+1]==n-1){
		rx=mxn2-1;
	}
	for(int z=mxn2,r=cntn2;z>=1 && lx<=rx;z/=2,r--){
		if(rx-z>=lx-1){
			if(rx>=n && rx-z+1>=n){
				continue;
			}
			if(r==0){
				add(rx-z+1,deep[p]+1,zz);
			}else{
				add(fa[rx-z+1][r-1],deep[p]+1,zz);
			}
			rx-=z;
		}
	}
	for(int z=mxn2,r=cntn2;z>=1 && ly<=ry;z/=2,r--){
		if(ly+z<=ry+1){
			if(r==0){
				add(ly,deep[willam_tree[p-1].rson]+1,zz);
			}else{
				add(fa[ly][r-1],deep[willam_tree[p-1].rson]+1,zz);
			}
			ly+=z;
		}
	}
}

int main(){
	lblock[0]=0;
	cin >> n >> q;
	while(mxn2<n){
		mxn2*=2;
		cntn2++;
	}
	for(int i=0;i<n;i++){
		cin >> a[i];
		if(numt==i+1){
			rblock[tot]=i-1;
			lblock[++tot]=i;
			numt*=2;
		}
		if(i==n-1){
			rblock[tot]=i;
		}
	}
	sum[1]=a[0];
	for(int i=2;i<=tot;i++){
		sum[lblock[i]]=a[lblock[i]];
		for(int j=lblock[i]+1;j<=rblock[i];j++){
			sum[j]=a[j]+sum[j-1];
			if(j==rblock[i]){
				allsums[i]=sum[j];
			}
		}
	}
	build(0,-1,1);
	for(int i=1; i<=mxn2; i++)
	{
	    lg[i]=lg[i-1]+(1<<lg[i-1]==i);
	}
	dfs(0,-1);
	while(q--){
		int opt,x,y;
		cin >> opt >> x >> y;
		if(opt==1){
			x--;
			update(x,y);
		}else{
			x--;
			y--;
			int deptx=deep[x-1]+1;
			int depty=deep[y]+1;
			cout << (ask(y,depty)+a[0])-(ask(x-1,deptx)+a[0]) << endl;
		}
	}
	return 0;
}