有关前缀和(后缀和)的一点定理(UVA1400, LA3938)

如果有想的不对的地方欢迎留言讨论

1. 已知在[L, R]区间中的最大前缀和的区间为[L, x], 则当a ∈ [L, R]时, 对于[a, R], 最大前缀和区间为 [a, x].

证明:

反证法, 若不为[a, x], 则[L, R]的最大前缀区间[L, x]也同样不应该以x为结尾.

[cpp]
Interval query_prefix(int o, int L, int R) { // 摘自代码仓库
if(max_prefix[o] <= qR) return make_pair(L, max_prefix[o]);
int M = L + (R-L)/2;
int lc = o*2, rc = o*2+1;
if(qR <= M) return query_prefix(lc, L, M);
Interval i = query_prefix(rc, M+1, R);
i.first = L;
return better(i, make_pair(L, max_prefix[lc])); // example
}
[/cpp]

上面的代码是一则例子.

最后一句中, i代表跨越中点M的情况, [L, max_prefix[lc]]代表没有跨越中点的情况, 运用上述定理. 这里的L即定理的a.

不难得出以下结论

2. 已知在[L, R]区间中的最大后缀和的区间为[x, R], 则当a ∈ [L, R]时, 对于[L, a], 最大后缀和区间为 [x, a].

证明:

反证法同上.

[cpp]
Interval query_suffix(int o, int L, int R) { // 摘自代码仓库
if(max_suffix[o] >= qL) return make_pair(max_suffix[o], R);
int M = L + (R-L)/2;
int lc = o*2, rc = o*2+1;
if(qL > M) return query_suffix(rc, M+1, R);
Interval i = query_suffix(lc, L, M);
i.second = R;
return better(i, make_pair(max_suffix[rc], R)); // example
}
[/cpp]

最后一句中, i代表跨越中点M的情况, [max_suffix[rc], R] 代表没有跨越中点的情况, 运用上述定理. 这里的R即定理的a.