【模板】树状数组区间最大

#include<bits/stdc++.h>

using namespace std;

int n, m, a[10000010], b[10000010];

int lb(int x)
{
	return x & (-x);
}

int query(int x, int y)
{
	int ans = 0;
	while(x <= y)
	{
		for(; 1; y -= lb(y))
		{
			if(y - lb(y) >= x) ans = max(ans, b[y]);
			else break; 
		}
		ans = max(ans, a[y]);
		y--;
	}
	return ans;
}

void updata(int pos)
{
	for(int i = pos; i <= n; i += lb(i))
	{
		b[i] = a[i];
		for(int k = 1; k <= lb(i); k <<= 1)
		b[i] = max(b[i], b[i - k]);
	}
}

int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
		updata(i);
	}
	for(int i = 1, q, c, d; i <= m; i++)
	{
		scanf("%d", &q);
		if(q == 1)
		{
			scanf("%d%d", &c, &d);
			a[c] += d;
			updata(c);
		}
		else 
		{
			scanf("%d%d", &c, &d);
			printf("%d\n", query(c, d));
		}
	}
	return 0;
}