: ※ 引述《FRAXIS (喔喔)》之铭言：
: 令 sum[i][j] = a[i] + ... + a[j] 是连续和
: 把 sum 画成一个矩阵
: 只有上三角，对角线是 a[0] 到 a[n-1]
: 目标是从上三角当中找到第k大
: 应该就是这样解吧？
: 只不过这个问题的阵列元素不是已知
: 所以要先算个前缀和，就能以O(1)时间求得阵列元素
我也有想过这样作，这样就可以摆脱掉 range。
令P[i] = A[1..i], P[0] = 0
SUM[i][j] = 结尾在 i 第 j 大的连续和
= P[i] - (P[0] ~ P[i-1] 中第 j 小数)
给定 (i, j) 利用 range median query 可以在O(lg n)时间内算出 SUM[i][j]
每一直列都是有序的，然后用 selection in sorted arrays 找出第 k 大元素。
时间复杂度会是O(n lg n) ~ O(n lg^3 n)
取决于 selection in sorted arrays 的效率。
不过这方法没办法解决 第 k 大 maximum density segment 问题。
我想到的方法都是基于 Theil-Sen estimator 的方法。