题目描述 Description
一行N个方格，开始每个格子里都有一个整数。现在动态地提出一些问题和修改：提问的形式是求某一个特定的子区间[a,b]中所有元素的和；修改的规则是指定某一个格子x，加上或者减去一个特定的值A。现在要求你能对每个提问作出正确的回答。1≤N<100000，,提问和修改的总数m<10000条。
输入描述 Input Description
输入文件第一行为一个整数N，接下来是n行n个整数，表示格子中原来的整数。接下一个正整数m，再接下来有m行，表示m个询问，第一个整数表示询问代号，询问代号1表示增加，后面的两个数x和A表示给位置X上的数值增加A，询问代号2表示区间求和，后面两个整数表示a和b，表示要求[a,b]之间的区间和。
输出描述 Output Description
共m行，每个整数
样例输入 Sample Input
6
4
5
6
2
1
3
4
1 3 5
2 1 4
1 1 9
2 2 6
样例输出 Sample Output
22
22
数据范围及提示 Data Size & Hint
1≤N≤100000， m≤10000 。
#include <cstdio>
#include <iostream>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn=;
using namespace std;
int sum[maxn<<]; void PushUP(int rt)
{
sum[rt]=sum[rt<<]+sum[rt<<|];//将两条小区间合并成一个大区间
} void build(int l,int r,int rt)
{
if (l==r)//最底层的节点
{
scanf("%d",&sum[rt]);//读入节点的值
return;
}
int m=(l+r)>>;//分成两个区间
build(lson);//分别搞搞左右两个区间
build(rson);
PushUP(rt);//将最底层的节点的值传入上层节点
} void update(int p,int add,int l,int r,int rt)
{
if (l==r)//往最底层节点加上add
{
sum[rt]+=add;
return;
}
int m=(l+r)>>;//取中间节点
if (p<=m)update(p,add,lson);//找到节点的儿子并且是p的祖先的节点，递归到p
else update(p,add,rson);
PushUP(rt);//更新p祖先节点的值
} int query(int L,int R,int l,int r,int rt)//区间查询
{//L，R是要查询的区间和，l、r是目前的区间，rt是目前的节点
if (L<=l&&r<=R)
{
return sum[rt];//如果当前区间是所求区间的一部分，就加上这段区间
}
int m=(l+r)>>;//二分当前区间
int ret=;//为所求区间的数值和
if (L<=m)ret+=query(L,R,lson);//加上所需区间
if (R>m)ret+=query(L,R,rson);
return ret;
} int main()
{
int n,m;
scanf("%d",&n);//区间为1-n
build(,n,);//建树
int cz;
cin>>m;
while(m--)
{
scanf("%d",&cz);
int a,b;
scanf("%d%d",&a,&b);
if (cz==)printf("%d\n",query(a,b,,n,));//query 询问区间的总值
//else if (cz==3)update(a,-b,1,n,1);//sub 往第a个数里减b
else update(a,b,,n,);//往第a个数中加b
}
return ;
}
给你N个数，有两种操作
1：给区间[a,b]的所有数都增加X
2：询问第i个数是什么？
输入描述 Input Description
第一行一个正整数n，接下来n行n个整数，再接下来一个正整数Q，表示操作的个数. 接下来Q行每行若干个整数。如果第一个数是1，后接3个正整数a,b,X，表示在区间[a,b]内每个数增加X,如果是2，后面跟1个整数i, 表示询问第i个位置的数是多少。
输出描述 Output Description
对于每个询问输出一行一个答案
样例输入 Sample Input
3
1
2
3
2
1 2 3 2
2 3
样例输出 Sample Output
5
数据范围及提示 Data Size & Hint
数据范围
1<=n<=100000
1<=q<=100000
#include <cstdio>
#include <iostream>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn=;
using namespace std;
int sum[maxn<<]; void PushUP(int rt)
{
sum[rt]=sum[rt<<]+sum[rt<<|];//将两条小区间合并成一个大区间
} void build(int l,int r,int rt)
{
if (l==r)//最底层的节点
{
scanf("%d",&sum[rt]);//读入节点的值
return;
}
int m=(l+r)>>;//分成两个区间
build(lson);//分别搞搞左右两个区间
build(rson);
PushUP(rt);//将最底层的节点的值传入上层节点
} void update(int p,int add,int l,int r,int rt)
{
if (l==r)//往最底层节点加上add
{
sum[rt]+=add;
return;
}
int m=(l+r)>>;//取中间节点
if (p<=m)update(p,add,lson);//找到节点的儿子并且是p的祖先的节点，递归到p
else update(p,add,rson);
PushUP(rt);//更新p祖先节点的值
} int query(int L,int R,int l,int r,int rt)//区间查询
{//L，R是要查询的区间和，l、r是目前的区间，rt是目前的节点
if (L<=l&&r<=R)
{
return sum[rt];//如果当前区间是所求区间的一部分，就加上这段区间
}
int m=(l+r)>>;//二分当前区间
int ret=;//为所求区间的数值和
if (L<=m)ret+=query(L,R,lson);//加上所需区间
if (R>m)ret+=query(L,R,rson);
return ret;
} int main()
{
int n,m;
scanf("%d",&n);//区间为1-n
build(,n,);//建树
int cz;
cin>>m;
while(m--)
{
scanf("%d",&cz);
int a,b,c;
if (cz==)
{
cin>>a>>b>>c;
for(int i=a;i<=b;++i)
update(i,c,,n,);
}
else
{
cin>>a;
cout<<query(a,a,,n,)<<endl;
}
}
return ;
}
题目描述 Description
给你N个数，有两种操作：
1：给区间[a,b]的所有数增加X
2：询问区间[a,b]的数的和。
输入描述 Input Description
第一行一个正整数n，接下来n行n个整数，
再接下来一个正整数Q，每行表示操作的个数，
如果第一个数是1，后接3个正整数，
表示在区间[a,b]内每个数增加X,如果是2，
表示操作2询问区间[a,b]的和是多少。
pascal选手请不要使用readln读入
输出描述 Output Description
对于每个询问输出一行一个答案
样例输入 Sample Input
3
1
2
3
2
1 2 3 2
2 2 3
样例输出 Sample Output
9
数据范围及提示 Data Size & Hint
数据范围
1<=n<=200000
1<=q<=200000
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 500005
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ll long long
ll sum[N*];
int visit[N*];
void pushUp(int rt)
{
sum[rt]=sum[rt<<]+sum[rt<<|];
} void build(int l,int r,int rt)
{
visit[rt]=;
if(l==r)
{
scanf("%lld",&sum[rt]);
return ;
}
int m=(l+r)>>;
build(lson);
build(rson);
pushUp(rt);
} void pushDown(int rt,int d)
{
if(visit[rt]!=)
{ visit[rt<<]+=visit[rt];
visit[rt<<|]+=visit[rt];
sum[rt<<|]+=(ll)(d>>)*visit[rt];
sum[rt<<]+=(ll)(d-(d>>))*visit[rt];
visit[rt]=;
}
} void update(int L,int R,int c,int l,int r,int rt)
{
if(L<=l && R>=r)
{
visit[rt]+=c;
sum[rt]+=(r-l+)*c;
return ;
}
pushDown(rt,r-l+);
int m=(l+r)>>;
if(L<=m)
update(L,R,c,lson);
if(R>m)
update(L,R,c,rson);
pushUp(rt);
} ll query(int L,int R,int l,int r,int rt)
{
if(L<=l&&R>=r)
{
return sum[rt];
}
pushDown(rt,r-l+);
int m=(l+r)>>;
ll ret=;
if(L<=m)
ret+=query(L,R,lson);
if(R>m)
ret+=query(L,R,rson);
return ret;
} int main()
{
int n,q,a,b,c;
int s;
scanf("%d",&n);
build(,n,);
cin>>q;
while(q--)
{
scanf("%d",&s);
if(s==)
{
scanf("%d%d%d",&a,&b,&c);
update(a,b,c,,n,);
}
else if(s==)
{
scanf("%d%d",&a,&b);
printf("%lld\n",query(a,b,,n,));
}
}
return ;
}