牛客小白月赛24 I.求和 （数状数组&DFS序）

题目传送门

思路：单点修改和区间查询。用DFS序形成一个数组。再用树状数组求和和更新。

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int tr[N],n,m,k,a[N],in[N],out[N],tot;//tr[]（tree[]数状数组) in[] out[]分别代表入栈,出栈时间. 
typedef long long ll;
#define lowbit(x) (x&-x)
vector<int>e[N];
int read(){ //快读 
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
void upd(int i,int x){//更新. 
	while(i<=n){
		tr[i]+=x;
		i+=lowbit(i);
	}
}
ll sum(int i){ //求和 
	ll sum=0;
	while(i) sum+=tr[i],i-=lowbit(i);
	return sum;
}
void dfs(int u,int fa){ //求dfs序 
	in[u]=++tot,upd(tot,a[u]);
	for(auto v:e[u]){
		if(v!=fa) dfs(v,u);
	}
	out[u]=tot;
}
int main(){
	n=read(),m=read(),k=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1,u,v;i<n;i++){
		u=read(),v=read();
		e[u].push_back(v),e[v].push_back(u);
	}
	dfs(k,0);
	while(m--){
		int op,a,x;
		op=read(),a=read();
		if(op==1) x=read(),upd(in[a],x);//这里数状数组下标是in[a]
		else printf("%lld\n",sum(out[a])-sum(in[a]-1));//区间和（类似前缀和求法) 
	}
	return 0;
}

补充：update原理：由左儿子向根扩展 所以是+lowbit(i)
sum原理：右向左倒退 所以是-lowbit(i)

附上树形图：