#牛客春招刷题训练营# https://www.nowcoder.com/practice/acead2f4c28c401889915da98ecdc6bf?channelPut=w25springcamp
观察本题,我们可以通过线段树去来记录前缀和,从而以O(logn)的复杂度完成每次查询
#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")