연속합 최대 Segment Tree

말 그대로 구간에서 최대 연속합을 구해주는 세그먼트 트리이다. 금광 세그로 유명하고, 금광 문제를 풀기 위해 배웠다. 아이디어가 신기함! 진한님의 코드를 적극 참고했습니다.

 

16993번: 연속합과 쿼리

 

#include<bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
typedef long long ll;
const ll INF=1e18;
struct Segment {
	struct node {
		ll sum,lmx,rmx,mx;
	};
	node base = {0,-INF,-INF,-INF};
	node f(node a,node b) {
		node res;
		res.sum=a.sum+b.sum;
		res.lmx=max(a.lmx,a.sum+b.lmx);
		res.rmx=max(a.rmx+b.sum,b.rmx);
		res.mx=max({a.mx,b.mx,a.rmx+b.lmx});
		return res;
	}
	int sz=1; vector<node> tree;
	Segment(int n) {
		while(sz<n) sz<<=1;
		tree.resize(2*sz);
	}
	void update(int i,int x) {
		for(tree[--i|=sz]={x,x,x,x};i>>=1;)
			tree[i]=f(tree[i<<1],tree[i<<1|1]);
	}
	node query(int l,int r,int i,int nl,int nr) {
		if(r<nl||nr<l) return base;
		if(l<=nl&&nr<=r) return tree[i];
		int mid=nl+nr>>1;
		return f(query(l,r,i<<1,nl,mid),query(l,r,i<<1|1,mid+1,nr));
	}
};
int main()
{
	fastio;
	int n; cin >> n;
	Segment tree(n);
	for(int i=1;i<=n;i++){
		int a; cin >> a;
		tree.update(i,a);
	}
	int q; cin >> q;
	while(q--){
		int i,j; cin >> i >> j;
		cout << tree.query(i,j,1,1,tree.sz).mx << '\n';
	}
}