专栏文章

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

GGs_The_Wolrd
P3374题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miphkg2v
此快照首次捕获于
2025/12/03 12:07
3 个月前
此快照最后确认于
2025/12/03 12:07
3 个月前
查看原文

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

题解区已经有很多奆佬了，希望可以夹缝求生。

题意

对一个数列进行两种操作：
  • 将一个数加上 xx。
  • 求 [x,y][x,y] 的前缀和。

思考

对于这道题，即使未引入树状数组，也有暴力和前缀和和差分可以解决。

非正解复杂度分析

暴力时间复杂度
  • 操作 1 O(1)O(1)。
  • 操作 2 最坏 O(n)O(n)。
mm 次操作时间复杂度最坏 O(nm)O(nm)。
pass。
前缀和差分时间复杂度
  • 预处理 O(n)O(n)。
  • 操作1 进行处理 O(n)O(n)。
  • 操作2 O(1)O(1)。
mm 次操作时间复杂度最坏 O(nm)O(nm)。
pass。
那我们就该引入树状数组了

算法分析

树状数组以二叉树为底层逻辑，二叉树是一种优秀的数据结构，许多以二叉树为底层的算法都可以将复杂度降为 log⁡\log 级别，树状数组也是如此。 这是一个树状数组示意图，其中 cc 数组就表示树状数组。树状数组每一个值都储存着这个位置所管理的前缀和。当我们要更新值的时候，重新处理前缀和只需要一层一层往上更新管理当前位置的值就行了。 此时我们就要引入一个函数lowbit。

核心函数

lowbit

lowbit是指将参数转为二进制后最后一个 11 所代表的位置，而在这里虽然不知道原理像是一个梯子，x+lowbit(x) x + lowbit(x) 就可以访问往上一层的下标。编码很简单，只有一行
CPP
int lowbit(int x) {return x & -x;}
我更喜欢取别名：
CPP
#define lowbit(x) x & -x;

更新值

理解上一个函数之后就很简单了：
CPP
/*可以把整个过程理解为爬梯子
|-------|
|-------|
|-------|   
|tree[x]| x 
x:当前位置 lowbit(x):往上一个台阶的距离 tree[x]:当前位置能管理到所有值的前缀和
*/
void update(int x,int d) //最开始在x 把a[x] 加上d
{
	while(x <= n)       //梯子最高就n层
	{
		tree[x] += d;     //当前位置加上d
		x += lowbit(x);   //往上一层
	}
}

求 [x,y][x,y] 前缀和

输出和普通前缀和差不多，用 sum(x) 表示 xx 的前缀和，输出 sum(x) - sum(y - 1) 就行了。
CPP
int sum(int x)
{
//和刚刚理解方法差不多 这里是下楼梯，顺便把所有的加上
  int ans = 0;      //答案
	while(x > 0)      //最少1层
	{
		ans += tree[x]; //加上值
		x -= lowbit(x); //往下
	}
	return ans;
}
至此所有的都分析完了。

AC Code

CPP
#include<bits/stdc++.h>
using namespace std;
#define pc putchar
#define lowbit(x) x & -x 
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 5e5 + 10;
int n,T;
int tree[maxn];
int op,x,y;
void update(int x,int d)
{
	while(x <= n)
	{
		tree[x] += d;
		x += lowbit(x); 
	}
} //更新部分
int sum(int x)
{
	int ans = 0;
	while(x > 0)
	{
		ans += tree[x];
		x -= lowbit(x); 
	}
	return ans;
} //前缀和
void solve()
{
	scanf("%d%d%d",&op,&x,&y);
	if(op == 1) update(x,y);                //操作1:更新
	else printf("%d\n",sum(y) - sum(x - 1));//操作2:前缀和
} //单词操作
int main()
{
	scanf("%d%d",&n,&T);
	for(int i=1;i<=n;i++) scanf("%d",&x),update(i,x);
  //这一行是初始化 更新当前值所有能管理到它的
	while(T --) solve();
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...