question：
有n个数，a[1]到a[n]。
接下来q次查询，每次动态指定两个数l,r，求a[l]到a[r]的最大子段和。
子段的意思是连续非空区间。
输入描述 Input Description
第一行一个数n。
第二行n个数a[1]~a[n]。
第三行一个数q。
以下q行每行两个数l和r。
输出描述 Output Description
q行，每行一个数，表示a[l]到a[r]的最大子段和。
样例输入 Sample Input
7
2 3 -233 233 -23 -2 233
4
1 7
5 6
2 5
2 3
样例输出 Sample Output
441
-2
233
3
高效完成这个问题，可以用线段树进行区间动态查询最大字段和
最大字段和
线段树实现
线段树维护：
1. 区间最大字段和
2. 从该区间的左端点开始的最大字段和（一定包括该区间左端点）
3. 从该区间的右端点开始的最大字段和（同理一定包括该区间右端点）
最大字段和分布
1. 完全的包含于做区间
2. 完全的包含于右区间
3. 包含于左右区间
维护的2,3主要是用于处理分布为3的情况
合并：很好理解
查询：
当查询区间完全处于当前区间的左侧
查询当前区间的左儿子
当查询区间完全处于当前区间的右侧
查询当前区间的由儿子
否则说明查询区间包含当前区间的ｍｉｄ
将ａｎｓ等置为０，从当前区间的左右儿子开始查询
会在3个黑圈处执行区间完全包含
从左到右依次编号1，2，3
会在1,2号return后进行一次ans， l_ans， r_ans 的赋max值
会在3好return后进行行一次ans， l_ans， r_ans 的赋max值
当递归到2,3节点时（注意这里是节点），进行一次
ans = max(max(L_ans, R_ans), L_rans + R_lans); l_ans = max(l_ans, T[jd << 1].w + R_lans); r_ans = max(r_ans, T[jd << 1 | 1].w + L_rans);
结束后ans即为answer
#include <iostream> #include <cstdio> #include <cstdio> #include <algorithm> #include <cmath> using namespace std; const int N = 4e6 + 1; #define LL long long #define zero 0 struct Node{ int l, r, w, max, l_max, r_max; }; Node T[N]; int n, m; struct R{ inline int reint(){ int x = 0, f = 1; char c = getchar(); while(c < '0' || c > '9'){ if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } inline LL rell(){ LL x = 0, f = 1; char c = getchar(); while(c < '0' || c > '9'){ if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } }re; void un(int jd){ T[jd].max = max(max(T[jd << 1].max, T[jd << 1 | 1].max), T[jd << 1].r_max + T[jd << 1 | 1].l_max); T[jd].l_max = max(T[jd << 1].l_max, T[jd << 1].w + T[jd << 1 | 1].l_max); T[jd].r_max = max(T[jd << 1 | 1].r_max, T[jd << 1 | 1].w + T[jd << 1].r_max); T[jd].w = T[jd << 1].w + T[jd << 1 | 1].w; return ; } void build_tree(int l, int r, int jd){ T[jd].l = l; T[jd].r = r; if(l == r){ T[jd].w = re.reint(); T[jd].l_max = T[jd].r_max = T[jd].max = T[jd].w; return ; } int mid = (l + r) >> 1; build_tree(l, mid, jd << 1); build_tree(mid + 1, r, jd << 1 | 1); un(jd); } void Q_ask(int l, int r, int jd, int x, int y, LL & ans, LL & l_ans, LL & r_ans){ if(x <= l && r <= y){ ans = T[jd].max; l_ans = T[jd].l_max; r_ans = T[jd].r_max; return ; } int mid = (l + r) >> 1; if(y <= mid) Q_ask(l, mid, jd << 1, x, y, ans, l_ans, r_ans); else if(x > mid) Q_ask(mid + 1, r, jd << 1 | 1, x, y, ans, l_ans, r_ans); else{ LL L_ans,L_lans, L_rans, R_ans, R_lans, R_rans; L_ans = L_lans = L_rans = R_ans = R_lans = R_rans = zero; Q_ask(l, mid, jd << 1, x, y, L_ans, L_lans, L_rans); Q_ask(mid + 1, r, jd << 1 | 1, x, y, R_ans, R_lans, R_rans); ans = max(max(L_ans, R_ans), L_rans + R_lans); l_ans = max(l_ans, T[jd << 1].w + R_lans); r_ans = max(r_ans, T[jd << 1 | 1].w + L_rans); } } int main(){ n = re.reint(); build_tree(1, n, 1); m = re.reint(); for(int i = 1; i <= m; i ++) { int x = re.reint(); int y = re.reint(); LL ans, l_ans, r_ans; ans = l_ans = r_ans = zero; Q_ask(1, n, 1, x, y, ans, l_ans, r_ans); printf("%lld ", ans); } return 0; }