题解 | 【模板】前缀和

#include <bits/stdc++.h>
#define LCHILD(p) (((p)<<1)|1)
#define RCHILD(P) (((p)+1)<<1)
#define int long long
using namespace std;
void solve()
{
    int n,m;
    cin>>n>>m;
    vector<int> data(n);
    for(int i=0;i<n;i++)
    {
        cin>>data[i];
    }
    struct node{
        int field;
    };
    vector<struct node> st(4*n);
    auto pushup=[&](int p)->void
    {
        st[p].field=st[LCHILD(p)].field+st[RCHILD(P)].field;
    };
    auto build=[&](auto&& build,int p,int left,int right)->void{
        if(left==right)
        {
            st[p].field=data[left];
            return;
        } 
        int mid=(left+right)>>1;
        build(build,LCHILD(p),left,mid);
        build(build,RCHILD(P),mid+1,right);
        pushup(p);
    };
    auto query=[&](auto&&query,int p,int left,int right,int qleft,int qright)->int{
        if(left>qright||right<qleft){
            return 0;
        }
        if(left>=qleft&&right<=qright)
        {
            return st[p].field;
        }
        int mid=(right+left)>>1;
        int q1=query(query,LCHILD(p),left,mid,qleft,qright);
        int q2=query(query,RCHILD(P),mid+1,right,qleft,qright);
        return q1+q2;
    };
    build(build,0,0,n-1);
    for(int i=0;i<m;i++)
    {
        int l,r;
        cin>>l>>r;
        cout<<query(query,0,0,n-1,l-1,r-1)<<endl;
    }
}
signed main() {
   int t=1;
   while(t--)
   {
    solve();
   } 
}
// 64 位输出请用 printf("%lld")

观察本题，我们可以通过线段树去来记录前缀和，从而以O(logn)的复杂度完成每次查询。