Rt，刚学了分块，然后把这道题当模板练了一下，显然$5\times 10^5 \times \sqrt {5 \times 10^5}=353,553,390$有点大，意料之中的TLE了，于是我尝试吸氧，结果……跑进了400ms。
代码：

#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
int st[1000],ed[1000],belong[500010],size[1000],data[1000];
int num;
int a[500010];
void init (int n)
{
	num = sqrt(n);
	for (int i = 1; i <= num; i++)
	{
		st[i] = n / num * (i - 1) + 1;
		ed[i] = n / num * i;
	}
	ed[num] = n;
	for (int i = 1; i <= num; i++)
	{
		for (int j = st[i]; j <= ed[i]; j++)
		{
    		belong[j] = i;
    		data[i]+=a[j];
		}
		size[i] = ed[i] - st[i] + 1;
	}
}
int query (int l,int r)
{
	int ans=0;
	int b=belong[l];
	if (l!=st[belong[l]])
	{
		for (int i=l;i<=min(ed[belong[l]],r);i++)
		{
			ans+=a[i];
			//cerr<<i<<endl;
		}
		b++;
	}
	//cerr<<ans<<endl;
	int e=belong[r];
	if (r!=ed[belong[r]])
	{
		for (int i=max(st[belong[r]],l);i<=r;i++)
		{
			ans+=a[i];
			//cerr<<i<<endl;
		}
		e--;
	}
	//cerr<<ans<<endl;
	for (int i=b;i<=e;i++)
	{
		ans+=data[i];
	}
	return ans;
}
void add (int x,int k)
{
	data[belong[x]]+=k;
	a[x]+=k;
}
inline int read()
{
	char c = getchar();
	int x = 0, f = 1;
	while (c < '0' || c > '9')
	{
    	if (c == '-')
			f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9')
	{
    	x = x * 10 + c - '0';
    	c = getchar();
	}
	return x * f;
}
int main ()
{
	int n,m;
	cin>>n>>m;
	for (int i=1;i<=n;i++)
	{
		a[i]=read();
	}
	init(n);
	for (int i=1;i<=m;i++)
	{
		int opt=read();
		if (opt==1)
		{
			int x=read(),k=read();
			add(x,k);
		}
		else
		{
			int l=read(),r=read();
			printf ("%d\n",query(l,r));
		}
	}
}

所以为什么能加快这么多？求助