有N个整数，对这N个整数构造一颗线段树，每个结点用一个sum保留所代表区间的和。

有Q个询问，第i个询问给出s[i]和t[i]，表示询问第s[i]个数至第t[i]个数的总和。

输入格式

第一行，N和Q。 1 <= N, Q <= 100000。

第二行，N个整数，每个整数范围[1,10^6]。

接下来有Q行，第i行是s[i]和t[i]。

输出格式

共Q行，每行一个整数。

#include<bits/stdc++.h>
using namespace std;
long long n,m,X,y,a[100005];
long long s[400005],tag[400005];
void pushdown(long long L,long long R,long long x)
{
    if(tag[x]!=0)
    {
        long long mid=(L+R)>>1;
        s[x<<1]+=(mid-L+1)*tag[x];
        s[x<<1|1]+=(R-mid)*tag[x];
        tag[x<<1]+=tag[x];
        tag[x<<1|1]+=tag[x];
        tag[x]=0;
    }
}
void pushup(long long x)
{
    s[x]=s[x<<1]+s[x<<1|1];
}
void buildtree(long long L,long long R,long long x)
{
    if(L==R)
    {
        s[x]=a[L];
        return;
    }
    long long mid=(L+R)>>1;
    buildtree(L,mid,x<<1);
    buildtree(mid+1,R,x<<1|1);
    pushup(x);
}
long long query(long long L,long long R,long long x,long long l,long long r)
{
    if(R<l||r<L)
        return 0;
    if(l<=L&&R<=r)
        return s[x];
    long long mid=(L+R)>>1;
    pushdown(L,R,x);
    return query(L,mid,x<<1,l,r)+query(mid+1,R,x<<1|1,l,r);
}
void update(long long L,long long R,long long x,long long l,long long r,long long val)
{
    if(R<l||r<L)
        return;
    if(l<=L&&R<=r)
    {
        s[x]+=(R-L+1)*val;
        tag[x]+=val;
        return;
    }
    long long mid=(L+R)>>1;
    pushdown(L,R,x);
    update(L,mid,x<<1,l,r,val);
    update(mid+1,R,x<<1|1,l,r,val);
    pushup(x);
}
int main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    buildtree(1,n,1);
    while(m--)
    {
        scanf("%lld%lld",&X,&y);
        printf("%lld\n",query(1,n,1,X,y));
    }
    return 0;
}