快速读写+线段树

#include<bits/stdc++.h>
#define read(x) {x=0;char z;while((z=getchar())<48);do x=x*10+(z^48);while((z=getchar())>47);}
using namespace std;

class segmentree
{
	private:
		vector<int> tree;
		int n;
		void build(vector<int> &a,int left,int right,int index)
		{
			if (left==right)
			{
				tree[index]=a[left];
				return;
			}
			int mid=(left+right)/2;
			build(a,left,mid,2*index+1);
			build(a,mid+1,right,2*index+2);
			tree[index]=tree[index*2+1]+tree[index*2+2];
		}
		int query(int ql,int qr,int left,int right,int index)
		{
			if (ql<=left && qr>=right)
				return tree[index];
			else if (qr<left || ql>right)
				return 0;
			int mid=(left+right)/2;
			return query(ql,qr,left,mid,index*2+1)+query(ql,qr,mid+1,right,index*2+2);
		}
	public:
		void build(vector<int> &a)
		{
			n=a.size();
			tree.resize(n*4,0);
			build(a,0,n-1,0);
		}
		int query(int ql,int qr)
		{
			return query(ql,qr,0,n-1,0);
		}
};
void output(int i)
{
    if (i>9) 
        output(i/10);
    putchar((i%10)|0x30);
    return;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n,m;
    read(n); read(m);
	vector<int> a(n);
    for (int i=0;i<n;i++)
        read(a[i]);
    segmentree seg;
    seg.build(a);
    while (m--)
    {
        int l,r;
        read(l); read(r);
        output(seg.query(l-1,r-1));
        putchar('\n');
    }
	return 0;
}