题目描述

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

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 的结果。

输入输出样例

输入

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

说明/提示

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

保证任意时刻数列中任意元素的和在 [−2^63,2^63) 内。

【样例解释】

思路

线段树的存储

线段树要用结构体存储

struct tree{int l,r;long long pre,add;
}t[4*maxn+2];

pre代表该节点维护的值，l，r代表该节点维护的区间范围 add涉及到lazy标记

建树

所谓建树，就是把数组a[1-n],放到线段树中。

在线段树中，对于一个区间（编号为p），他的左儿子为2p，右儿子为2p+1。

void bulid(int p,int l,int r){t[p].l=l;t[p].r=r;//以p为编号的节点维护的区间为l到rif(l==r){//l=r的话，这个区间就只有一个数，直接让区间维护的值等于a[i]t[p].pre=a[l];return;}//否则维护的值等于左儿子加右儿子int mid=l+r>>1;bulid(p*2,l,mid);bulid(p*2+1,mid+1,r);t[p].pre=t[p*2].pre+t[p*2+1].pre;
} 

lazy标记

懒标记的精髓就是打标记和下传操作，由于我们要做的操作是区间加一个数，所以我们不妨在区间进行修改时为该区间打上一个标记，就不必再修改他的儿子所维护区间，等到要使用该节点的儿子节点维护的值时，再将懒标记下放即可，可以节省很多时间，对于每次区间修改和查询，将懒标记下传，可以节省很多时间。

void spread(int p){if(t[p].add){//如果懒标记不为0，就将其下传，修改左右儿子维护的值t[p*2].pre+=t[p].add*(t[p*2].r-t[p*2].l+1);t[p*2+1].pre+=t[p].add*(t[p*2+1].r-t[p*2+1].l+1);t[p*2].add+=t[p].add;//为该节点的左右儿子打上标记t[p*2+1].add+=t[p].add;t[p].add=0;//下传之后将该节点的懒标记清0}
}

-区间修改

考虑将一个区间加上一个数，我们可以从根节点不断向下查找，当发现我们要修改的区间覆盖了当前节点时，我们就把这个区间给修改，并打上懒标记（由于懒标记存在，我们就不必再修改他的儿子节点），否则下传懒标记，继续向下找

void change(int p,int x,int y,int z){if(x<=t[p].l && y>=t[p].r){//被覆盖的话，就对其进行修改t[p].pre+=(long long)z*(t[p].r-t[p].l+1);t[p].add+=z;//打上懒标记return;}spread(p);//如果发现没有被覆盖，那就需要继续向下找，考虑儿子所维护的区间可能因为懒标记的存在而没有修改，因此将懒标记下放int mid=t[p].l+t[p].r>>1;if(x<=mid) change(p*2,x,y,z);//如果要修改的区间覆盖了左儿子，就修改左儿子if(y>mid) change(p*2+1,x,y,z);//右儿子同理t[p].pre=t[p*2].pre+t[p*2+1].pre;//最终维护的值等于左儿子的值+右儿子的值   
}

区间查询

考虑询问一个区间的和，依旧是从根节点向下查找，当发现该节点被覆盖时，就返回维护的值，否则下传懒标记，查询左右儿子，累加答案

long long ask(int p,int x,int y){if(x<=t[p].l && y>=t[p].r) return t[p].pre;//如果被覆盖，就返回维护的值spread(p);//下传懒标记，并查询左右儿子int mid=t[p].l+t[p].r>>1;long long ans=0;if(x<=mid) ans+=ask(p*2,x,y);if(y>mid) ans+=ask(p*2+1,x,y);//累加答案，返回左右儿子的和return ans;
}

代码

 

#include<iostream>
#include<iomanip>
#include<algorithm>
#include<math.h>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
const int N = 5e5 + 5;
ll a[N];
struct node 
{ll l, r, lazy, sum;
}tree[N << 2];
void pushup(ll x)
{tree[x].sum = tree[2 * x].sum + tree[2 * x + 1].sum;
}
void bulid(ll x, ll l, ll r)
{if (l == r){tree[x] = { l,l,0,a[l] };}else{tree[x] = { l,r,0 };ll mid = l + r >> 1;bulid(2 * x, l, mid);bulid(2 * x + 1, mid + 1, r);pushup(x);}
}
void pushdown(ll x)
{tree[x * 2].sum += tree[x].lazy*(tree[x * 2].r - tree[x * 2].l + 1);tree[x * 2 + 1].sum += tree[x].lazy*(tree[x * 2 + 1].r - tree[x * 2 + 1].l + 1);tree[x * 2].lazy += tree[x].lazy;tree[x * 2 + 1].lazy += tree[x].lazy;tree[x].lazy = 0;
}
void update(ll x, ll l, ll r, ll d)
{if (tree[x].l >= l && tree[x].r <= r){tree[x].sum += d * (tree[x].r - tree[x].l + 1);tree[x].lazy += d;}else{pushdown(x);ll mid = tree[x].l + tree[x].r >> 1;if (l <= mid){update(2 * x, l, r, d);}if(r > mid){update(2 * x + 1, l, r, d);}pushup(x);}
}
ll query(ll x, ll l, ll r)
{if (tree[x].l >= l && tree[x].r <= r){return tree[x].sum;}else{pushdown(x);ll mid = tree[x].l + tree[x].r >> 1;ll res = 0;if (l <= mid){res += query(2 * x, l, r);}if(r > mid){res += query(2 * x + 1, l, r);}return res;}
}
int main()
{ios::sync_with_stdio(0), cin.tie(0);int n, m;cin >> n >> m;for (int i = 1; i <= n; ++i){cin >> a[i];}bulid(1, 1, n);while (m--){int o;cin >> o;if (o == 1){ll x, y, k;cin >> x >> y >> k;update(1, x, y, k);}else{ll x, y;cin >> x >> y;cout << query(1, x, y) << endl;}}return 0;
}