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

题目大意：

有一个由

n

个数字组成的数列，对于第

i

个数其初始值为

i

，对这个数列进行

m

次操作：

操作1：将第 $x$ 个数加 $k$ 。
操作2：输出 $a$ 数组中 $[x,y]$ 区间内的和，包括 $a[x]$ 和 $a[y]$ 。

算法分析：

由于

n

和

m

的范围均为

5 \times 10^5

，因此暴力绝对不可取，考虑使用树状数组解决。

关于树状数组：

简介：树状数组的学名是二叉搜索树，其利用二叉树思想的前缀和的加强版。
与二叉树的区别：简单来说，树状数组比二叉树少了大部分非叶子节点的子节点。以下两幅图帮助理解：

（1）一个倾斜的二叉树

（2）其对应的树状数组

观察后可发现，一个二叉树如果只保留每一列最上面的一个节点，就是其对应的树状数组。
在本题的运用：单点修改，区间查询。

介绍一个新的概念，

lowbit

：

对于一个正整数 $x$ ，我们规定 $lowbit(x)$ 为：二进制表示的 $x$ ，除最后一位 $1$ 外，其余全部改为 $0$ ，所得到的数。
一般将 $lowbit(i)$ 用于求 $a[i]$ 的父节点。

CPP

inline int lowbit(int x){
	return x&(-x);
}

Code:

CPP

#include<bits/stdc++.h>
using namespace std;
int n,m,a[500005],c[500005];
inline int lowbit(int x){
	return x&(-x);
}
void add(int i,int x){//将第i个数增加x。
	while(i<=n){
		c[i]+=x;
		i+=lowbit(i);
	}
}
int query(int x){//求a[x]到a[y]的区间和。
	int s=0;
	while(x){
		s+=c[x];
		x-=lowbit(x);
	}
	return s;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		add(i,a[i]);//为每个结点赋初值。
	}
	int op,x,y;
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&op,&x,&y);
		if(op==1){//将a[x]的值加y。
			a[x]+=y;
			add(x,y);
		}else{
			printf("%d\n",query(y)-query(x-1));//输出区间和。
		}
	}
    return 0;
}

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

文章操作

题目大意：

算法分析：

Code:

相关推荐

评论

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