最大子区间和

洛谷 P4513 小白逛公园

题目概要

给定一个整数数组 nums，每次进行以下两种操作之一：

• 区间查询：给定两个整数 l 和 r，求 nums[l，r] 的最大子区间和。
• 单点更新：给定一个整数 i 和一个整数 val，将 nums[i] 改为 val。

解法

信息维护

线段树维护

• pref[i]：区间最大前缀和
• suf[i]：区间最大后缀和
• sum[i]：区间总和
• sub[i]：区间最大子区间和

状态转移

l 表示左子树，r 表示右子树

• 最大前缀和：在左半边或在右半边 pref[i] = max(pref[l], sum[l] + pref[r])

l			r
pref[l]		1	1	1	1
sum[l] + pref[r]				1	1

• 最大后缀和：在左半边或在右半边 suf[i] = max(suf[r], sum[r] + suf[l])

l			r
1	1	1	1	suf[r]
1		sum[r] + suf[l]

• 区间总和：左半边加右半边 sum[i] = sum[l] + sum[r]

l			r
sum[l]	sum[r]

• 区间最大子区间和：在左半边、右半边或横跨两半 sub[i] = max(sub[l], sub[r], suf[l] + pref[r])

l			r
sub[l]		1	1	sub[r]
1	suf[l] + pref[r]			1	1