【问题描述】
题目来源:https://www.luogu.com.cn/problem/P3374
如题,已知一个数列,你需要进行下面两种操作:
• 将某一个数加上 x;
• 求出某区间每一个数的和。
【输入格式】
第一行包含两个正整数 n,m,分别表示该数列数字的个数和操作的总个数。
第二行包含 n 个用空格分隔的整数,其中第 i 个数字表示数列第 i 项的初始值。
接下来 m 行每行包含 3 个整数,表示一个操作,具体如下:
• 1 x k 含义:将第 x 个数加上 k;
• 2 x y 含义:输出区间 [x,y] 内每个数的和。
【输出格式】
输出包含若干行整数,即为所有操作 2 的结果。
【输入输出样例】
输入:
5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4
输出:
14
16
【算法分析】
本题是树状数组的模板题,即实现树状数组的经典操作“单点更新,区间查询”。关于树状数组的知识点详见:
https://blog.csdn.net/hnjzsyjyj/article/details/120559543
https://blog.csdn.net/hnjzsyjyj/article/details/120573850
【数据范围】
对于 30% 的数据,1≤n≤8,1≤m≤10
对于 70% 的数据,1≤n,m≤10^4
对于 100% 的数据,1≤n,m≤5×10^5
【算法代码】
#include <bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
int c[maxn];
int n,m;
int lowbit(int i) {
return (-i)&i; //返回树状数组每个c[i]所包含的元素个数
}
void update(int i,int val) { //点更新,创建树状数组c[i]
while(i<=n) {
c[i]+=val;
i+=lowbit(i); //i的后继(父结点)
}
}
int preSum(int i) { //前缀和
int s=0;
while(i>0) { //树状数组的下标从1开始
s+=c[i];
i-=lowbit(i); //i的前驱
}
return s;
}
int segSum(int i,int j) { //区间和
return preSum(j)-preSum(i-1);
}
int main() {
scanf("%d%d",&n,&m);
memset(c,0,sizeof(c));
int val;
for(int i=1; i<=n; i++) { //下标从1开始
scanf("%d",&val);
update(i,val); //构建树状数组
}
while(m--) {
int k,u,v,x;
scanf("%d",&k);
if(k==1) {
scanf("%d%d",&u,&x);
update(u,x);
} else {
scanf("%d%d",&u,&v);
printf("%d\n",segSum(u,v));
}
}
return 0;
}
/*
in:
5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4
out:
14
16
*/
【参考文献】
https://www.luogu.com.cn/problem/P3374
https://www.luogu.com.cn/problem/solution/P3374
https://blog.csdn.net/hnjzsyjyj/article/details/120559543
https://blog.csdn.net/hnjzsyjyj/article/details/120573850
https://www.luogu.com.cn/problem/P2073
https://www.luogu.com.cn/problem/P3368