最大子段和的各种形式

题解内附每道题的 题意 题目链接 思路

SPOJ 1043 GSS1

静态区间求个最大子段和，

题解

SPOJ 1577 GSS2

和1一样，区别是若区间内存在相同的元素，则该元素只计算一次。

离线一下然后使劲跑。。

题解

SPOJ 1716 GSS3

和1一样，就是要支持单点修改

题解

SPOJ 2713 GSS4

==普通线段树，感觉和这系列关系不大。

题解

SPOJ 2916 GSS5

题意有点怪，，跟3差不多，就是稍加强了点询问

题解

SPOJ 4487 GSS6

和3也差不多。就是区间可以翻转移动啥的。

splay

题解

SPOJ 6779 GSS7

在静态的树上询问任意路径的最大子段和 以及单点修改

因为树的结构不会变，所以在线段树上剖分就可以了

题解

SPOJ GSS系列 最大子段和 线段树+树链剖分+splay 1043 1557 1716 2713 2916 4487 6779