本题要求输入一个序列$a$，求$m$个区间$[l,r]$的最大前缀和

因为是$10^5$的区间查询，考虑$O(nlogn)$的线段树

由于不带修，只需要思考查询和建树

首先是建树，考虑如何合并左右区间：显然，应考虑左右区间谁更优，所以应该为$max(\text{左区间最大前缀和},\text{右区间最大前缀和+左区间的和})$，所以需要每个节点记录2个值，分别为求和和区间最大前缀和。下面是建树参考代码。

void build(int l,int r,int id){
	if(l==r){
		f[id].sum=f[id].qsum=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(l,mid,id<<1);
	build(mid+1,r,(id<<1)|1);
	f[id]=node(f[id<<1].sum+f[(id<<1)|1].sum,max(f[id<<1].qsum,f[(id<<1)|1].qsum+f[id<<1].sum));
}

然后是区间查询，主要分为三种情况

• 本区间完全被包含在查询区间中 (ql<=l&&qr>=r)
• 本区间的左子区间部分被包含在查询区间中 (mid>=ql)
• 本区间的右子区间部分被包含在查询区间中 (mid+1<=qr)

若完全包含，直接返回，否则分别向下递归即可

注意分别向下递归时不应该直接返回答案，应该合并左右区间再返回答案，因为有可能左右区间都符合（即查询区间被本区间完全包含）

贴下区间查询的代码

node query(int l,int r,int id,int ql,int qr){
	if(ql<=l&&qr>=r) return f[id];
	int mid=(l+r)>>1;
	ll ans1=0,ans2=-1e9;
	if(mid>=ql){
		node ret=query(l,mid,id<<1,ql,qr);
		ans1+=ret.sum;
		ans2=max(ans2,ret.qsum);
	}
	if(mid+1<=qr){
		node ret=query(mid+1,r,(id<<1)|1,ql,qr);
		ans2=max(ans2,ret.qsum+ans1);
		ans1+=ret.sum;
	}
	return node(ans1,ans2);
}

建树，查询写完了，就很简单了，只需注意以下几点就行

• 线段树开4倍空间
• 求和可能很大，要用long long存
• 不要忘记输入输出优化

最后贴上完整代码

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <deque>
#include <iomanip>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#define ll long long
#define pii pair<int,int>
#define p(i,j) make_pair(i,j)
using namespace std;
int n,m,x,y,z,a[1000010],sum,ans,cnt,tmp,tot,k,T,l,r;
struct node{
	ll sum,qsum;
	node(ll __=0,ll ___=0){sum=__,qsum=___;}
}f[1000010];
void build(int l,int r,int id){
	if(l==r){
		f[id].sum=f[id].qsum=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(l,mid,id<<1);
	build(mid+1,r,(id<<1)|1);
	f[id]=node(f[id<<1].sum+f[(id<<1)|1].sum,max(f[id<<1].qsum,f[(id<<1)|1].qsum+f[id<<1].sum));
}
node query(int l,int r,int id,int ql,int qr){
	if(ql<=l&&qr>=r) return f[id];
	int mid=(l+r)>>1;
	ll ans1=0,ans2=-1e9;
	if(mid>=ql){
		node ret=query(l,mid,id<<1,ql,qr);
		ans1+=ret.sum;
		ans2=max(ans2,ret.qsum);
	}
	if(mid+1<=qr){
		node ret=query(mid+1,r,(id<<1)|1,ql,qr);
		ans2=max(ans2,ret.qsum+ans1);
		ans1+=ret.sum;
	}
	return node(ans1,ans2);
}
int main(){
	std::ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	build(1,n,1);
	while(m--){
		cin>>l>>r;
		node ans=query(1,n,1,l,r);
		cout<<ans.qsum<<"\n";
	}
	return 0;
}

这样你就搓出来了一棵线段树