P3372 【模板】线段树 1

luoguP3372

【模板】线段树 1

题目描述

如题，已知一个数列，你需要进行下面两种操作：

1. 将某区间每一个数加上 $k$。
2. 求出某区间每一个数的和。

输入格式

第一行包含两个整数 $n,m$，分别表示该数列数字的个数和操作的总个数。

第二行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个数字表示数列第 $i$ 项的初始值。

接下来 $m$ 行每行包含 $3$ 或 $4$ 个整数，表示一个操作，具体如下：

1. 1 x y k：将区间 $[x,y]$ 内每个数加上 $k$。
2. 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

提示

对于 $30\%$ 的数据：$n\le 8$，$m\le 10$。
对于 $70\%$ 的数据：$n\le {10}^3$，$m\le {10}^4$。
对于 $100\%$ 的数据：$1\le n,m\le {10}^5$。

保证任意时刻数列中所有元素的绝对值之和 $\le {10}^{18}$。

【样例解释】

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+2;
ll a[N],tr[N],tag[N];
int n,m;
int mi(int l,int r)
{return (l+r)>>1;	
}
void pushup(int rt)
{tr[rt]=tr[rt<<1]+tr[(rt<<1)|1];return ;
}
void build(int rt,int l,int r)
{tag[rt]=0;if(l==r){tr[rt]=a[l];return ;}int mid=mi(l,r);build(rt<<1,l,mid);build((rt<<1)|1,mid+1,r);pushup(rt);return ;
}
void pushdown(int rt,int l,int r)
{int mid=mi(l,r);int rt_r=rt<<1,rt_l;rt_l=rt_r|1;tag[rt_r]=tag[rt_r]+tag[rt];tr[rt_r]+=tag[rt]*(mid-l+1);tag[rt_l]=tag[rt_l]+tag[rt];tr[rt_l]+=tag[rt]*(r-mid);tag[rt]=0;
}
void update(int rt,int l,int r,int al,int ar,ll k)
{
//	printf("%d %d %d al:%d ar:%d %d\n",rt,l,r,al,ar,k);if(al<=l&&r<=ar){tr[rt]+=k*(r-l+1);tag[rt]+=k;return ;}pushdown(rt,l,r);int mid=mi(l,r);if(al<=mid)update(rt<<1,l,mid,al,ar,k);if(ar>mid)update((rt<<1)|1,mid+1,r,al,ar,k);pushup(rt);return ;
}
ll query(int rt,int l,int r,int ql,int qr)
{ll res=0;if(ql<=l&&qr>=r)return tr[rt];
//	puts("o");int mid=mi(l,r);pushdown(rt,l,r);if(ql<=mid)res+=query(rt<<1,l,mid,ql,qr);if(qr>mid)res+=query((rt<<1)|1,mid+1,r,ql,qr);return res;
}
int main(){scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%lld",&a[i]);build(1,1,n);while(m--){int op;scanf("%d",&op);if(op==1){int x,y;ll k;scanf("%d%d%lld",&x,&y,&k);update(1,1,n,x,y,k);}else {int x,y;scanf("%d%d",&x,&y);printf("%lld\n",query(1,1,n,x,y));}}return 0;
}
/*
5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4#include<bits/stdc++.h>
#define MAXN 1000001
#define ll long long
using namespace std;
unsigned ll n,m,a[MAXN],tr[MAXN<<2],tag[MAXN<<2];
inline ll ls(ll x){ return x<<1;}
inline ll rs(ll x){ return x<<1|1;}
inline void pushup(ll rt){tr[rt]=tr[ls(rt)]+tr[rs(rt)];
}
void build(ll rt,ll l,ll r){tag[rt]=0;if(l==r){ tr[rt]=a[l]; return ;}ll mid=(l+r)>>1;build(ls(rt),l,mid);build(rs(rt),mid+1,r);pushup(rt);
} 
inline void pushdown(ll rt,ll l,ll r){ll mid=(l+r)>>1;tag[ls(rt)]=tag[ls(rt)]+tag[rt];tr[ls(rt)]=tr[ls(rt)]+tag[rt]*(mid-l+1);tag[rs(rt)]=tag[rs(rt)]+tag[rt];tr[rs(rt)]=tr[rs(rt)]+tag[rt]*(r-mid);tag[rt]=0;
}
inline void update(ll rt,ll nl,ll nr,ll l,ll r,ll k){if(nl<=l&&r<=nr){tr[rt]+=k*(r-l+1);tag[rt]+=k;return ;}pushdown(rt,l,r);ll mid=(l+r)>>1;if(nl<=mid) update(ls(rt),nl,nr,l,mid,k);if(nr>mid) update(rs(rt),nl,nr,mid+1,r,k);pushup(rt);
}
ll query(ll rt,ll qx,ll qy,ll l,ll r){ll res=0;if(qx<=l&&r<=qy)return tr[rt];ll mid=(l+r)>>1;pushdown(rt,l,r);if(qx<=mid) res+=query(ls(rt),qx,qy,l,mid);if(qy>mid) res+=query(rs(rt),qx,qy,mid+1,r);return res;
}
int main(){ll a1,b,c,d,e,f;cin>>n>>m;for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);build(1,1,n);while(m--){scanf("%lld",&a1);if(a1==1){scanf("%lld%lld%lld",&b,&c,&d);update(1,b,c,1,n,d);}if(a1==2){scanf("%lld%lld",&e,&f);printf("%lld\n",query(1,e,f,1,n));}}return 0;
}*/