#include
#include
#define ll long long
using namespace std;
const int Maxn = 1000005;
ll d[4 * Maxn], tag[Maxn * 4];//注意该大小大概为所有单个值数量的四倍
ll a[Maxn];inline void pushup(ll p) {//建树,先在pushup前面递归到最底层然后向上递归建树,确定节点值.
//(p << 1) | 1意思是2*p+1,为了加快运算速度使用位运算
d[p] = d[p << 1] + d[(p << 1) | 1];
}
inline void build(ll l, ll r, ll p) {//建立线段树
if (l == r) {//如果以及递归到单个元素节点则开始返回,以单个节点为根本开始pushup
d[p] = a[l];
return;
}
ll mid = l + ((r - l) >> 1);//求中间值
//递归
build(l, mid, p << 1);//区间的左子节点
build(mid + 1, r, (p << 1) | 1);//p<<1表示2*p 此时最后一位一定是0,或1,则相当于加1
pushup(p);//建树求值
}inline void pushdown(ll s, ll t, ll p) {//由更改的区间向下更改求值
ll mid = s + ((t - s) >> 1);
d[p << 1] += tag[p] * (mid - s + 1), d[(p << 1) | 1] += tag[p] * (t - mid);
tag[p << 1] += tag[p], tag[(p << 1) | 1] += tag[p]; // 将标记下传给子节点
tag[p] = 0;
return;
}inline void update(ll l, ll r, ll s, ll t, ll p, ll c) {//l,r 表示修改区间,[s, t] 为当前节点包含的区间,
// p为当前节点的编号,c为要修改的值
if (l <= s && t <= r) {
d[p] += (t - s + 1) * c;
tag[p] += c;
return;
}// 当前区间为修改区间的子区间时直接修改当前节点的值,然后打标记,结束修改//如果不是,向下修改查询
if (tag[p])
pushdown(s, t, p);//先将上一次修改时tag中要修改的数向下修改
int mid = s + ((t - s) >> 1);
if (l <= mid)update(l, r, s, mid, p << 1, c);
if (r > mid) update(l, r, mid + 1, t, (p << 1) | 1, c);
pushup(p);//向上更改求值???
}
ll query(ll l, ll r, ll s, ll t, ll p)//查询l,r为要查询区间,st为当前节点所包含区间
{
if (l <= s && t <= r)return d[p];//如果该节点已经是查询区间或完整的是查询区间中的一部分,则结束递归返回
ll mid = s + ((t - s) >> 1);//求中值
if (tag[p]) {//如果该区间有标记值,则向下查询前应先pushdown更新子区间的值
pushdown(s, t, p);
}
ll ans = 0;//求解
if (l <= mid)ans = query(l, r, s, mid, p << 1);//开始时ans无值可以直接赋值
if (r > mid) ans += query(l, r, mid + 1, t, (p << 1) | 1);//要加上上面那行的值
return ans;//返回
}
int main()
{
ll n, m, e;
ll x;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
}
build(1, n, 1);
ll a1, b1, c1;
while (m--)
{
scanf("%lld", &x);
if (x == 1) {
scanf("%lld%lld%lld", &a1, &b1, &c1);
update(a1, b1, 1, n, 1, c1);
}
else {
scanf("%lld%lld", &a1, &b1);
printf("%lldn", query(a1, b1, 1, n, 1));
}
}
return 0;
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)