A Simple Problem with Integers(树状数组)
程序员文章站
2024-03-03 16:06:34
...
A Simple Problem with Integers
题目传送门
A Simple Problem with Integers
题目大意
给你一个长度为n的数组
进行m次操作,操作包括对区间的值进行加减和对区间进行求和
思路
区间更新,区间查询的树状数组
考虑使用更加简单的树状数组,区间更新可以使用差分维护,区间查询可以开两个数组维护
AC Code
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=1e6 +9;
int n, m;
int a[N];
int sum1[N]; //(D[1] + D[2] + ... + D[n])
int sum2[N]; //(1*D[1] + 2*D[2] + ... + n*D[n])
int lowbit(int x){
return x&(-x);
}
void updata(int i,int k){
int x = i; //因为x不变,所以得先保存i值
while(i <= n){
sum1[i] += k;
sum2[i] += k * (x-1);
i += lowbit(i);
}
}
int getsum(int i){ //求前缀和
int res = 0, x = i;
while(i > 0){
res += x * sum1[i] - sum2[i];
i -= lowbit(i);
}
return res;
}
void solve(){
cin>>n>>m;
for(int i = 1; i <= n; i++){
cin>>a[i];
updata(i,a[i] - a[i-1]); //输入初值的时候,也相当于更新了值
}
while(m--){
int x, y, k;
string c;
cin>>c;
if(c=="Q"){
cin>>x>>y;
cout<<getsum(y)-getsum(x-1)<<endl;
}
else if(c=="C"){
cin>>x>>y>>k;
updata(x,k), updata(y+1,-k);
}
}
return ;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
solve();
return 0;
}
推荐阅读
-
A Simple Problem with Integers(树状数组)
-
【线段树】【模板】讲解 + 例题1 HDU - 1754 I Hate It (点修改分数)+ 例题二 POJ - 3468 A Simple Problem with Integers(区间加值)
-
poj3468A Simple Problem with Integers解题报告(线段树成段增减 & 区间求和)
-
POJ 3468 A Simple Problem with Integers (线段树+成段更新)
-
北京大学OpenJudge 3243 A Simple Problem with Integers (线段树区间求和)
-
CF #261 div2 D. Pashmak and Parmida's problem (树状数组
-
CF #261 div2 D. Pashmak and Parmida's problem (树状数组