P3374 【模板】树状数组 1（单点修改，区间查询）

铺垫

我们知道，一个数可以分解成多个

2^n

形式的数，也就是说，我们如果要求一个数组前

x

个数的和，例如我们要求出前六个数的和，只用求出从

2^0=1

长度为

2^2=4

的和与从

2^2+1=5

长度为

2

的和并相加就可以求出前六个数的和。

我们知道，

6=(110)_2

也就是

(10)_2+(100)_2

所以我们只需要求出一个数二进制的末尾

0

的数量就可以进行拆分从而显著提高查找效率，这里就要引用 int lowbit(int n){return n&(-n);}。也就是求一个数二进制末位的

1

加上若干个连续的

0

的二进制数的数值。

实现方法

我们可以构建一个如上图的树状数组，很显然，当一个编号为

n

的节点改变时，编号为

n+\operatorname{lowbit}(n)

的节点也要相应改变。因此，我们便将编号为

n+\operatorname{lowbit}(n)

的节点称为编号为

n

的节点的后继。

以样例为例，我们就可以得到一个这样的初始树状数组。也就是说，一个节点的值是他所有以这个节点为后继的节点的数值之和。修改也同理，只需要将需要修改的节点的所有后继修改就可以了。这样我们就可以得到修改函数了，平均时间复杂度为

O(\log n)

。

CPP

void g(int now,int x){
	if(now>n) return;
	f[now]+=x;
	g(now+lowbit(now),x);
}

查询也同理，如果我们要查询（初始数组）前三个数的和，只需要将树状数组中第二个节点的值与第三个节点的值相加，也就是

6+4=1+5+4=10

，换言之，我们只需要一直往前搜索编号为

n

的节点前驱也就是编号为

n-\operatorname{lowbit}(n)

的数值并求和就是前

n

个数的和。

CPP

unsigned long long co(int x){return x>0?co(x-lowbit(x))+f[x]:0;}

AC代码

CPP

#include <bits/stdc++.h>
using namespace std;
unsigned long long f[100000005],n,w,a,b,c,t;
int lowbit(int n){return n&(-n);}
void g(int now,int x){
	if(now>n) return;
	f[now]+=x;
	g(now+lowbit(now),x);
}
unsigned long long co(int x){return x>0?co(x-lowbit(x))+f[x]:0;}
int main(){
	cin>>n>>w;
	for(int i=1;i<=n;i++){
		cin>>t;
		g(i,t);
	}
	for(int i=0;i<w;i++){
		cin>>a>>b>>c;
		if(a==1){
			g(b,c);
		}else{
			cout<<co(c)-co(b-1)<<endl;
		}
	}
	return 0;
}

题解：P3374 【模板】树状数组 1

文章操作

P3374 【模板】树状数组 1（单点修改，区间查询）

铺垫

实现方法

AC代码

相关推荐

评论

题解：P3374 【模板】树状数组 1