题目描述
给定一个长度为n（n<=100000），初始值都为0的序列，x(x<=10000)次的修改某些位置上的数字，每次加上一个数，然后提出y (y<=10000)个问题，求每段区间的和。时间限制1秒。
输入输出格式
输入格式：
第一行1个数，表示序列的长度n
第二行1个数，表示操作的次数w
后面依次是w行，分别表示加入和询问操作
其中，加入用x表示，询问用y表示
x的格式为"x a b" 表示在序列a的位置加上b
y的格式为"y a b" 表示询问a到b区间的加和
输出格式：
每行一个数，分别是每次询问的结果
输入输出样例
输入样例#1：
复制
5
4
x 3 8
y 1 3
x 4 9
y 3 4
输出样例#1：
复制
8
17线段数做法：
// luogu-judger-enable-o2
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define maxn 100007
using namespace std;
int n,m,x,y,z;
char jjj[
4];
long long Sum[maxn<<
2],Add[maxn<<
2];
int A[maxn];
void PushUp(
int rt){Sum[rt]=Sum[rt*
2]+Sum[rt*
2+
1];}
void Build(
int l,
int r,
int rt){
if(l==
r) {
Sum[rt]=
A[l];
return;
}
int m=(l+r)>>
1;
Build(l,m,rt<<
1);
Build(m+
1,r,rt<<
1|
1);
PushUp(rt);
}
void PushDown(
int rt,
int ln,
int rn){
if(Add[rt]){
Add[rt<<
1]+=
Add[rt];
Add[rt<<
1|
1]+=
Add[rt];
Sum[rt<<
1]+=Add[rt]*
ln;
Sum[rt<<
1|
1]+=Add[rt]*
rn;
Add[rt]=
0;
}
}
long long Query(
int L,
int R,
int l,
int r,
int rt){
if(L <= l && r <=
R)
return Sum[rt];
int m=(l+r)>>
1;
PushDown(rt,m-l+
1,r-
m);
long long ANS=
0;
if(L <= m) ANS+=Query(L,R,l,m,rt<<
1);
if(R > m) ANS+=Query(L,R,m+
1,r,rt<<
1|
1);
return ANS;
}
void Update(
int L,
int R,
int C,
int l,
int r,
int rt){
if(L <= l && r <=
R){
Sum[rt]+=C*(r-l+
1);
Add[rt]+=
C;
return ;
}
int m=(l+r)>>
1;
PushDown(rt,m-l+
1,r-
m);
if(L <= m) Update(L,R,C,l,m,rt<<
1);
if(R > m) Update(L,R,C,m+
1,r,rt<<
1|
1);
PushUp(rt);
}
int main(){
while(scanf(
"%d%d",&n,&m)!=
EOF){
for(
int i=
1;i<=n;i++
)
A[i]=
0;
Build(1,n,
1);
while(m--
)
{
scanf("%s",jjj);
if(jjj[
0]==
'x') {
scanf("%d%d",&x,&
z);
Update(x,x,z,1,n,
1);
}
else {
scanf("%d%d",&x,&
y);
printf("%lld\n",Query(x,y,
1,n,
1));
}
}
}
return 0;
}
树状数组解法如下：
’
#include<iostream>
using namespace std;
const int MAXN=
100000+
2;
int a[MAXN];
int n,w;
int lowbit(
int x){
return x&(-
x);
}
void add(
int p,
int x){
while(p<=
n){
a[p]+=
x;
p+=
lowbit(p);
}
}
int ask(
int p){
int ans=
0;
while(p>
0){
ans+=
a[p];
p-=
lowbit(p);
}
return ans;
}
int main(){
cin>>n>>
w;
for(
int i=
1;i<=w;i++
){
char q;
int y,z;
cin>>q>>y>>
z;
if(q==
'x') add(y,z);
else cout<<ask(z)-ask(y-
1)<<
endl;
}
return 0;
}
转载于:https://www.cnblogs.com/wuhu-JJJ/p/11205996.html
相关资源：各显卡算力对照表！
