某岛

… : "…アッカリ~ン . .. . " .. .
June 29, 2012

【套题】GSS 系列

Brief description:

序列 a 的 l, r 之间的最大子段和 (Maximum subsequence sum) 定义为:
Query(l, r) = Max {a[i]+a[i+1]+…+a[j] ; l ≤ i ≤ j ≤ r}.

GSS 系列是 SPOj 上的一组数据结构习题,一共 6 题,大部分是和最大字段和有关。

GSS1: 只有询问。GSS3:单点修改。
GSS5: 询问时,限定区间两端点 i, j 的取值范围。
GSS2、GSS4:相对的独立问题。。
GSS6: 加入插入和删除操作。
GSS7: 树上 GSS 问题。

Analysis:

Level 1.
GSS1 / GSS3 / GSS5

Level 2.
GSS4 / GSS2

Level 3.
GSS6 / GSS7

External link:

http://www.spoj.pl/problems/GSS1/
http://www.spoj.pl/problems/GSS2/
http://www.spoj.pl/problems/GSS3/
http://www.spoj.pl/problems/GSS4/
http://www.spoj.pl/problems/GSS5/
http://www.spoj.pl/problems/GSS6/
http://www.spoj.pl/problems/GSS7/