题解：P3368 【模板】树状数组 2

题目大意

树状数组模板题，要求在

1 \leq N, M\le 500000

的数据下实现区间加和单点查询。

大体思路

树状数组教学

树状数组其实是一个相当优美的算法了，其中使用的 lowbit 十分精妙。

CPP

//lowbit
int lowbit(int k){
	return k&(-k);
}

lowbit 的含义是什么呢？为什么 lowbit 能够这么快速的实现此类问题呢，我们先来看一张图（from OI-Wiki）。

这里运用了负数的存储特性，负数是用补码存储的，例如当

i

为奇数时，最后一位是

1

取反加一并没有进位，所以

lowbit

结果正好是

1

，相同的我们可以推得，如果

i

为偶数，结果是

k\le i

最大的

2^k

，其中

k

为整数，有兴趣的小伙伴可以自己分类讨论推导一下，探讨偶数时可以分成

2^k

和

y\times 2^k

两种，然后就可以发现后者其实是用一个奇数左移

k

位来表示的（说多了）。

2^k=lowbit(k)

，发现

lowbit(i)

刚好是满足上图的，上图恰好满足

C[i] = A[i - 2^k+1] + A[i - 2^k+2] + ... + A[i]

。

举个例子，

lowbit(1)=1

，正好

C[1]

就是存

A[1-1+1](A[1])

，

lowbit(2)=2

，正好

C[2]

就是存

A[2-2+1]+A[2-2+2](A[1]+A[2])

，

lowbit(3)=1

，

C[3]

就是存

A[3-1+1](A[3])

。

也就是说，树状数组通过使用 lowbit 来存储一部分节点，能用很少的空间实现一部分线段树的功能，而且常数较小。

回到本题

本题中，由于一开始的数是固定的，所以我们只需要用树状数组来记录变更的值。

区间修改单点查询，我们使用差分数组思想。

区间加

我们要进行的区间加操作，需要从

x

扫到

n

，对差分数组进行操作。

CPP

void add(int x,int k){
	while(x<=n){
		t[x]+=k;
		x+=lowbit(x);
	}
}

毕竟是差分数组，所以我们在主函数内调用时需要这样。

CPP

add(x,z);
add(y+1,-z);

单点查询

我们要进行单点查操作，就需要从

x

扫到

0

，每一个修改都要加起来，就是把差分前缀和起来。

CPP

int sum(int x){
	int ans=0;
	while(x){
		ans+=t[x];
		x-=lowbit(x);
	}
	return ans;
}

Code

CPP

#include<bits/stdc++.h>
using namespace std;
int n,m;
int t[500005];int a[500005];
int lowbit(int k){
	return k& -k;
}
void add(int x,int k){
	while(x<=n){
		t[x]+=k;
		x+=lowbit(x);
	}
}
int sum(int x){
	int ans=0;
	while(x){
		ans+=t[x];
		x-=lowbit(x);
	}
	return ans;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=m;i++){
		int c;
		cin>>c;
		if(c==1){
			int x,y,z;
			cin>>x>>y>>z;
			add(x,z);
			add(y+1,-z);
		}
		else{
			int x;
			cin>>x;
			int ans=sum(x)+a[x];
			cout<<ans<<endl;
		}
	}
    return 0;
}

题解：P3368 【模板】树状数组 2

文章操作

题目大意

大体思路

树状数组教学

回到本题

Code

相关推荐

评论

题解：P3368 【模板】树状数组 2