【套題】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/