题目类型：差分，线段树

传送门：>Here<

题意：给出一个数列，每次给一个区间对应的加上一个等差数列，并询问某一个元素目前的值。

解题思路

所谓差分，我个人的理解就是用\(O(1)\)的方法来维护前缀和，当然查询变为了\(O(n)\)。差分就好像将前缀和变成了一个数一样——当一段区间需要全部加上\(k\)时：差分数组某一位上\(+k\)，意味着这之后的所有元素都将\(+k\)。就好像一条带子拖到最后了。因此我们如果仅仅操作一个区间的话，那么要把后面多出来的带子减掉，于是我们再另外加一条负的带子在后面。

刚才谈论整个区间都加一个相同的数。如果整个区间加的是一个等差数列呢？相当于这个区间内所加的数，每个都比前面的多加\(d\)。效果就等价于在差分数组中，令这个区间的每个元素加上\(d\)。然后末尾要减去末项。依然使用刚才的比喻，将那么多条相同的带子依次叠放，假设区间长度是\(l\)，那么最后一个元素那里肯定放着\(l\)条带子了。而我们在最后需要把这\(l\)条带子全部减掉。

因此，如果用差分来维护这道题，我们来总结一下步骤：（按照题意，等差数列的更新方法是\(l \ r \ k \ d\)，代表左端点，右端点，首项，公差；设差分数组为\(s\)）

• 令\(s[l]+=k\)

• 令\(s[l+1..r]+=d\)

• 令\(s[r+1]-=k+d*(r-l)\)（末项）

由此我们发现，对于大多数的情况都是\(+d\)，因此转化为一个区间更新的问题。差分数组的统计方法我们已经很熟悉了，需要从头遍历。因此元素\(p\)现在的值应该是：初始值 + \(s[1..p]\)，因此转化为一个区间查询的问题

因此我们可以用线段树方便地\(O(logn)\)维护好

反思

一直以为差分和线段树维护的几乎是同一个东西，却从来没想过线段树可以用来维护差分！线段树维护差分，就好像求和的和。然而等差数列就好像是三维的一样，先由差分转化为二维，然后由线段树转化为线性。

正好像我们在找规律时所作的一样，差，差之差，差之差之差。那么这道题就好像倒过来，和，和的和，和的和的和……

Code

不需要建树，线段树写起来好像异常短小精悍……\(qwq\)

/*By DennyQi 2018*/

#include <cstdio>

#include <queue>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXN = 100010;

const int INF = 1061109567;

inline int Max(const int a, const int b){ return (a > b) ? a : b; }

inline int Min(const int a, const int b){ return (a < b) ? a : b; }

inline int read(){

    int x = 0; int w = 1; register char c = getchar();

    for(; c ^ '-' && (c < '0' || c > '9'); c = getchar());

    if(c == '-') w = -1, c = getchar();

    for(; c >= '0' && c <= '9'; c = getchar()) x = (x<<3) + (x<<1) + c - '0'; return x * w;

}

int N,M,opt,l,r,x,y;

int a[MAXN];

int val[MAXN<<2],lazy[MAXN<<2];

struct SegmentTree{

	inline void pushdown(int rt, int l, int r){

		if(lazy[rt]){

			int mid = (l+r)/2;

			val[rt<<1] += lazy[rt] * (mid-l+1);

			val[rt<<1|1] += lazy[rt] * (r-(mid+1)+1);

			lazy[rt<<1] += lazy[rt];

			lazy[rt<<1|1] += lazy[rt];

			lazy[rt] = 0;

		}

	}

	int query(int rt, int l, int r, int x, int y){

		if(l > y || r < x) return 0;

		if(x <= l && r <= y) return val[rt];

		pushdown(rt, l, r);

		int mid = (l+r)/2;

		return query(rt<<1,l,mid,x,y) + query(rt<<1|1,mid+1,r,x,y);

	}

	void update(int rt, int l, int r, int x, int y, int k){

		if(l > y || r < x) return;

		if(x <= l && r <= y){

			lazy[rt] += k;

			val[rt] += (r-l+1) * k;

			return;

		}

		pushdown(rt,l,r);

		int mid = (l+r)/2;

		update(rt<<1,l,mid,x,y,k), update(rt<<1|1,mid+1,r,x,y,k);

		val[rt] = val[rt<<1] + val[rt<<1|1];

	}

}qxz;

int main(){

	N = read(), M = read();

	for(int i = 1; i <= N; ++i){

		a[i] = read();

	}

	while(M--){

		opt = read();

		if(opt == 1){

			l = read(), r = read(), x = read(), y = read();

			qxz.update(1,1,N,l,l,x);

			qxz.update(1,1,N,l+1,r,y);

			qxz.update(1,1,N,r+1,r+1,-(x+y*(r-l)));

		}

		else{

			x = read();

			printf("%d\n", qxz.query(1,1,N,1,x)+a[x]);

		}

	}

	return 0;

}