Description：

单点修改，区间历史最小和。

$1\leqslant n\leqslant 10^5$

Solution：

首先把询问 $(l,r)$ 放在二维平面上，那么一次单点加操作可以看成是一次矩形加操作，查询是查询单点历史最小值，于是还是维护值，标记，历史最小值，历史最小标记，和在序列上一样，只不过要用二维数据结构，我写了 $KDT$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n,m;

#define MAXN 100010

typedef long long ll;

int a[MAXN];

ll sum[MAXN];

struct query

{

	int op,x,y;

}q[MAXN];

struct point

{

	int d[2],id;

}p_[MAXN],p[MAXN];

int D;

bool cmp_D(point a,point b){return (a.d[D] == b.d[D] ? a.d[D ^ 1] < b.d[D ^ 1] : a.d[D] < b.d[D]);}

int cnt = 0,tot = 0;

struct node

{

	int lc,rc;

	int d[2],mn[2],mx[2];

	ll val,minval,tag,mintag;

}t[MAXN];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

void maintain(int rt)

{

	t[rt].mn[0] = t[rt].mx[0] = t[rt].d[0];t[rt].mn[1] = t[rt].mx[1] = t[rt].d[1];

	if(t[rt].lc)

	{

		int lc = t[rt].lc;

		t[rt].mn[0] = min(t[rt].mn[0],t[lc].mn[0]);t[rt].mx[0] = max(t[rt].mx[0],t[lc].mx[0]);

		t[rt].mn[1] = min(t[rt].mn[1],t[lc].mn[1]);t[rt].mx[1] = max(t[rt].mx[1],t[lc].mx[1]);

	}

	if(t[rt].rc)

	{

		int rc = t[rt].rc;

		t[rt].mn[0] = min(t[rt].mn[0],t[rc].mn[0]);t[rt].mx[0] = max(t[rt].mx[0],t[rc].mx[0]);

		t[rt].mn[1] = min(t[rt].mn[1],t[rc].mn[1]);t[rt].mx[1] = max(t[rt].mx[1],t[rc].mx[1]);

	}

	return;

}

void pushdown(int rt)

{

	if(t[rt].lc)

	{

		int lc = t[rt].lc;

		t[lc].mintag = min(t[lc].mintag,t[lc].tag + t[rt].mintag);

		t[lc].minval = min(t[lc].minval,t[lc].val + t[rt].mintag);

		t[lc].val += t[rt].tag;t[lc].tag += t[rt].tag;

	}

	if(t[rt].rc)

	{

		int rc = t[rt].rc;

		t[rc].mintag = min(t[rc].mintag,t[rc].tag + t[rt].mintag);

		t[rc].minval = min(t[rc].minval,t[rc].val + t[rt].mintag);

		t[rc].val += t[rt].tag;t[rc].tag += t[rt].tag;

	}

	t[rt].tag = t[rt].mintag = 0;

	return;

}

int mv[MAXN],len[MAXN];

void build(int &rt,int l,int r,int type)

{

	if(l > r)return;

	rt = newnode();

	int mid = ((l + r) >> 1);

	D = type;sort(p + l,p + r + 1,cmp_D);

	t[rt].d[0] = p[mid].d[0];t[rt].d[1] = p[mid].d[1];

	t[rt].val = t[rt].minval = sum[p[mid].d[1]] - sum[p[mid].d[0] - 1];//cout << rt << " " << p[mid].d[0] << " " << p[mid].d[1] << " " << t[rt].val << endl;

	for(int i = l;i <= mid - 1;++i)++len[p[i].id],mv[p[i].id] = mv[p[i].id] << 1 | 0;

	build(t[rt].lc,l,mid - 1,type ^ 1);

	for(int i = mid + 1;i <= r;++i)++len[p[i].id],mv[p[i].id] = mv[p[i].id] << 1 | 1;

	build(t[rt].rc,mid + 1,r,type ^ 1);

	maintain(rt);

	return;

}

int in(int rt,int lx,int rx,int ly,int ry)

{

	if(lx <= t[rt].mn[0] && t[rt].mx[0] <= rx && ly <= t[rt].mn[1] && t[rt].mx[1] <= ry)return 1;

	if(lx > t[rt].mx[0] || rx < t[rt].mn[0] || ly > t[rt].mx[1] || ry < t[rt].mn[1])return -1;

	return 0;

}

int in2(int rt,int lx,int rx,int ly,int ry)

{

	if(lx <= t[rt].d[0] && t[rt].d[0] <= rx && ly <= t[rt].d[1] && t[rt].d[1] <= ry)return 1;

	else return 0;

}

void add(int rt,int lx,int rx,int ly,int ry,ll v)

{

	int id = in(rt,lx,rx,ly,ry);

	if(id == -1)return;

	if(id == 1)

	{

		t[rt].val += v;

		t[rt].tag += v;

		t[rt].mintag = min(t[rt].mintag,t[rt].tag);

		t[rt].minval = min(t[rt].minval,t[rt].val);

		return;

	}

	if(in2(rt,lx,rx,ly,ry))

	{

		t[rt].val += v;

		t[rt].minval = min(t[rt].minval,t[rt].val);

	}

	pushdown(rt);

	add(t[rt].lc,lx,rx,ly,ry,v);

	add(t[rt].rc,lx,rx,ly,ry,v);

	return;

}

ll query(int id)

{

	int cur = root;

	for(int i = len[id] - 1;i >= 0;--i)

	{

		pushdown(cur);

		if(((mv[id] >> i) & 1) == 0)cur = t[cur].lc;

		if(((mv[id] >> i) & 1) == 1)cur = t[cur].rc;

	}//cout << cur << endl;

	return t[cur].minval;

}

map<pair<int,int>,int> ps;

int main()

{

	freopen("ds.in","r",stdin);

	freopen("ds.out","w",stdout);

	n = rd();m = rd();

	for(int i = 1;i <= n;++i)a[i] = rd();

	for(int i = 1;i <= n;++i)sum[i] = sum[i - 1] + a[i];

	for(int i = 1;i <= m;++i)

	{

		q[i].op = rd();q[i].x = rd();q[i].y = rd();

		if(q[i].op == 2){++cnt;p_[cnt].d[0] = q[i].x;p_[cnt].d[1] = q[i].y;}

	}

	for(int i = 1;i <= cnt;++i)if(i == 1 || p_[i].d[0] != p_[i - 1].d[0] || p_[i].d[1] != p_[i - 1].d[1])p[++tot] = p_[i];

	for(int i = 1;i <= tot;++i)p[i].id = i,ps[make_pair(p[i].d[0],p[i].d[1])] = i;

	build(root,1,tot,0);

	for(int i = 1;i <= m;++i)

	{

		if(q[i].op == 1)

		{

			add(root,1,q[i].x,q[i].x,n,q[i].y - a[q[i].x]);

			a[q[i].x] = q[i].y;

		}

		else

		{

			printf("%lld\n",query(ps[make_pair(q[i].x,q[i].y)]));

		}

	}

	fclose(stdin);

	fclose(stdout);

	return 0;

}