Hard
327. Count of Range Sum
arraybinary-searchdivide-and-conquerbinary-indexed-treesegment-treemerge-sortordered-set
解題說明
Count of Range Sum
題目描述：給定一個整數陣列 nums 和兩個整數 lower、upper，求有多少個連續子陣列的和 S 滿足 lower <= S <= upper。
解題思路：先計算前綴和陣列 prefix，使得子陣列 [i, j] 的和 = prefix[j+1] - prefix[i]。問題轉化為：對每個 j，計算有多少個 i < j 使得 lower <= prefix[j] - prefix[i] <= upper，即 prefix[j] - upper <= prefix[i] <= prefix[j] - lower。利用歸併排序，在合併兩個有序子陣列的過程中，用雙指標高效計算跨越左右半部的合法配對數量。整體時間複雜度為 O(n log n)。
C++ 解法
複雜度分析
時間複雜度：O(n log n) — 歸併排序的分治結構，每層的雙指標掃描總計 O(n)，共 O(log n) 層。
空間複雜度：O(n) — 前綴和陣列佔 O(n)，歸併排序的暫存空間佔 O(n)。
虛擬碼
1. Compute prefix sum array: prefix[0] = 0, prefix[i+1] = prefix[i] + nums[i]
2. Define mergeCount(prefix, lo, hi, lower, upper):
a. Base case: if lo >= hi, return 0
b. mid = (lo + hi) / 2
c. count = mergeCount(lo, mid) + mergeCount(mid+1, hi)
d. For each i in [lo, mid]:
- Find leftmost index 'left' in [mid+1, hi] where prefix[left] - prefix[i] >= lower
- Find leftmost index 'right' in [mid+1, hi] where prefix[right] - prefix[i] > upper
- count += right - left
e. Merge prefix[lo..mid] and prefix[mid+1..hi] in sorted order
f. Return count
3. Return mergeCount(prefix, 0, n, lower, upper)其他解法
BIT / 線段樹 + 離散化 O(n log n)：將前綴和離散化後，從左到右遍歷。對每個 prefix[j]，在 BIT 中查詢落在 [prefix[j]-upper, prefix[j]-lower] 範圍內的已插入前綴和數量，再將 prefix[j] 插入。需要離散化步驟，實作較複雜。
有序集合（如平衡 BST）O(n log n)：使用 C++ 的 std::multiset 或 policy-based tree，每次插入後用 order_of_key 查詢範圍內的計數。常數因子較大但思路直觀。
延伸思考
- 如果要求出具體的子陣列而非僅計數，該如何修改？
- 歸併排序方法能否推廣到計算逆序對數量？兩者有什麼關聯？
- 如果 lower 和 upper 會動態改變（線上查詢），哪種方法更適合？