[洛谷P4513]小白逛公园[线段树]

题面

双倍经验: https://www.luogu.org/problem/SP1716

复习一下线段树, 老是写挂…

这道题是一种常见线段树处理连续子段问题的做法. 每个节点维护区间最大子段和, 从左端点开始的最大子段和, 从右端点开始的最大子段和, 区间和. 这样合并两个节点时就可以考虑以下几种情况:

对于合并后的从左端点开始的最大子段和有: 保持原样; 子段跨越mid(左儿子区间和+右儿子左端).

合并后的右端点开始的最大子段和同理.

对于合并后的区间最大子段和有: 子段全在左儿子; 全在右儿子; 子段跨越mid(左儿子右端+右儿子左端).

赞(0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址