討論串[問題] 第 k 大連續子陣列和
共 5 篇文章
內容預覽:
這算是經典的最大連續子陣列和的變形吧。. 給定一個長度為 n 的整數陣列，和一個正整數 k 。. 找出一個在所有 C(n, 2) 個連續子陣列中，總和第 k 大的連續子陣列。. 理論上是可以做到 O(n)，但是這方法應該不實用。. 雖然也有其他的O(n lg n)，O(n lg^2 n)和O(n l
(還有171個字)
內容預覽:
最近剛好有遇到類似的問題. 我想你問的應該是靜態問題而不是動態問題吧？. 令 sum[i][j] = a[i] + ... + a[j] 是連續和. 把 sum 畫成一個矩陣. 只有上三角，對角線是 a[0] 到 a[n-1]. 整個結構類似 pascal 三角形，. 不過這裡是越右上越大，右上角是
(還有480個字)
內容預覽:
說到 RANGE. 最近剛好有學到一個 fourier transform 的方法 分享一下. 時間複雜度是 O(n + RANGE log RANGE). 首先計算前綴和 prefix_sum(x) = a[0] + ... + a[x]. 連續和就是 prefix_sum(j) - prefix
(還有635個字)
內容預覽:
我也有想過這樣作，這樣就可以擺脫掉 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 可以
(還有191個字)
內容預覽:
我在思考樹上的 k 大路徑時找到了一個比較容易做的o(n^2)方法。. （bzoj 3784）. 用陣列的中點把陣列切成兩半，計算通過中點的子陣列和，然後分別遞迴. 兩邊計算不通過中點的子陣列和，就可以找到第 k 大了。. 計算通過中點的子陣列和時，. 把左半邊每個元素到中點的子陣列和算出並排序，設
(還有305個字)