【模板】线段树 1
题目描述
如题，已知一个数列 \{a_i\}，你需要进行下面两种操作：
- 将某区间每一个数加上 k。
- 求出某区间每一个数的和。
输入格式
第一行包含两个整数 n, m，分别表示该数列数字的个数和操作的总个数。
第二行包含 n 个用空格分隔的整数 a_i，其中第 i 个数字表示数列第 i 项的初始值。
接下来 m 行每行包含 3 或 4 个整数，表示一个操作，具体如下：
1 x y k：将区间 [x, y] 内每个数加上 k。2 x y：输出区间 [x, y] 内每个数的和。
输出格式
输出包含若干行整数，即为所有操作 2 的结果。
输入输出样例 #1
输入 #1
5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4
输出 #1
11
8
20
说明/提示
对于 15\% 的数据：n \le 8，m \le 10。
对于 35\% 的数据：n \le {10}^3，m \le {10}^4。
对于 100\% 的数据：1 \le n, m \le {10}^5，a_i,k 为正数，且任意时刻数列的和不超过 2\times 10^{18}。
【样例解释】
样例不对，输出
11
8
16
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int MAX_N=1e6+10;
const int MX=100;
const ll BASE=131;
const ll MOD=10000000007;
const int mxN=84;
const int mxK=14;
const int MAXSIZE=300;
ll n,m,z[MAX_N];
typedef struct ST{
ll sum[MAX_N],ans[MAX_N];
inline ll lch(int x){return x<<1;}
inline ll rsh(int x){return x<<1|1;}
inline void pushup(ll x){ans[x]=ans[lch(x)]+ans[rsh(x)];return;}
inline void solve(ll a,ll b,ll c,ll d){
sum[a]=sum[a]+d;
ans[a]=ans[a]+d*(b-c+1);
return;
}
inline void pushdown(ll a,ll l,ll r){
ll mid=(l+r)>>1;
solve(lch(a),l,mid,sum[a]);
solve(rsh(a),mid+1,r,sum[a]);
sum[a]=0;
return;
}
inline void biuding(ll a,ll l,ll r,ll *v){
sum[a]=0;
if(l==r){ans[a]=v[l];}
else{
ll mid=(l+r)>>1;
biuding(lch(a),l,mid,v);
biuding(rsh(a),mid+1,r,v);
pushup(a);
}
return;
}
inline void toUP(ll tl,ll tr,ll l,ll r,ll a,ll b){
if(tl<=l&&r<=tr){ans[a]+=b*(r-l+1);sum[a]+=b;return;}
pushdown(a,l,r);
ll mid=(l+r)>>1;
if(tl<=mid)toUP(tl,tr,l,mid,lch(a),b);
if(tr>mid)toUP(tl,tr,mid+1,r,rsh(a),b);
pushup(a);
return;
}
inline ll range(ll tl,ll tr,ll l,ll r,ll a){
ll cnt=0;
if(tl<=l&&r<=tr)return ans[a];
ll mid=(l+r)>>1;
pushdown(a,l,r);
if(tl<=mid)cnt+=range(tl,tr,l,mid,lch(a));
if(tr>mid)cnt+=range(tl,tr,mid+1,r,rsh(a));
return cnt;
}
}ST;
ST tr;
int main(){
cin>>n>>m;
ll a,b,c,d;
for(ll i=1;i<=n;i++)cin>>z[i];
tr.biuding(1,1,n,z);
for(ll i=0;i<m;i++){
cin>>a;
if(a==1){
cin>>b>>c>>d;
tr.toUP(b,c,1,n,1,d);
continue;
}
cin>>b>>c;
ll ans=tr.range(b,c,1,n,1);
printf("%lld\n",ans);
}
return 0;
}