#1024. 线段树1
线段树1
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 100005;
ll tree[N*4],tag[N*4];
int n,m,a[N];
void pushup(int rt)
{
tree[rt] = tree[rt<<1] + tree[rt<<1|1];
}
void pushdown(int l,int r,int rt)
{
if(tag[rt]){
tag[rt<<1] += tag[rt];
tag[rt<<1|1] += tag[rt];
int mid =(l+r)>>1;
tree[rt<<1] += tag[rt]*(mid-l+1);
tree[rt<<1|1] += tag[rt]*(r-mid);
tag[rt] = 0;
}
}
void build(int l,int r,int rt)
{
if(l==r){
tree[rt] = a[l];
return;
}
int mid = (l+r)>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
pushup(rt);
}
void update(int l,int r,int rt,int L,int R,int c)
{
if(L<=l && r<=R){
tag[rt]+=c;
tree[rt]+=(r-l+1)*c;
return;
}
pushdown(l,r,rt);
int mid = (l+r)>>1;
if(L<=mid)update(l,mid,rt<<1,L,R,c);
if(R>mid)update(mid+1,r,rt<<1|1,L,R,c);
pushup(rt);
}
ll query(int l,int r,int rt,int L,int R)
{
if(L<=l && r<=R){
return tree[rt];
}
pushdown(l,r,rt);
ll sum = 0;
int mid = (l+r)>>1;
if(L<=mid)sum+=query(l,mid,rt<<1,L,R);
if(R>mid)sum+=query(mid+1,r,rt<<1|1,L,R);
return sum;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
build(1,n,1);
while(m--){
int pos,x,y,z;
cin>>pos>>x>>y;
if(pos==1){
cin>>z;
update(1,n,1,x,y,z);
}
else cout<<query(1,n,1,x,y)<<endl;
}
return 0;
}
题目描述
如题,已知一个数列,你需要进行下面两种操作:
- 将某区间每一个数加上 。
- 求出某区间每一个数的和。
输入格式
第一行包含两个整数 ,分别表示该数列数字的个数和操作的总个数。
第二行包含 个用空格分隔的整数,其中第 个数字表示数列第 项的初始值。
接下来 行每行包含 或 个整数,表示一个操作,具体如下:
1 x y k
:将区间 内每个数加上 。2 x y
:输出区间 内每个数的和。
输出格式
输出包含若干行整数,即为所有操作 2 的结果。
5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4
11
8
20
提示
对于 的数据:,。 对于 的数据:,。 对于 的数据:。
保证任意时刻数列中任意元素的和在 内。
【样例解释】