首先 range sum 可以透過累加總和計算 sum of nums[a:b] = nums[0:b] - nums[0:a] 先計算 cumulative sum array 這題是分治法 考慮如何從 f(start, mid) 和 f(mid, end) 的解 得出 f(start, end) 的解 分切到 f(i, i) = 0 合併時 loop 左邊，start to mid, index i 右邊兩個指針 a b, from mid while [a] - [i] < lower; a++ while [b] - [i] <= upper; b++ 這樣 a b 就會停在元素 [i] 符合範圍的位置 count += b - a 看了很久我都不確定對不對 … 我是感受不出為什麼 b - a 獲得解

另一種作法，不知道對不對 枚舉左界，二分搜右界可以的範圍

先猜一個，還沒實作： 枚舉每個 index i 的 prefix sum，假設為 a，每次處理完 a 就把它丟到某個資料結構裡面 對於每個 a，要找有多少個先前的 prefix sum b，滿足 lower <= a - b <= upper，也就是 a - upper <= b <= a - lower 所以會需要一個資料結構可以快速 query 某個範圍內有多少個點 這個資料結構可以是 1. Segment tree：update 跟 query 都可以 O(logN) 做到，但這題的數字範圍挺大的，而且沒辦法離散化，可能會需要動態開點，而且就算動態開點效率可能也不會特別好 2. Balanced binary search tree：每一次查詢比 a - upper 跟 a - lower 大 / 小的元素的 index，index 相減就知道有多少符合條件的 b Python 實作可以用 SortedList() 配合 bisect_left 找 index，這樣整體複雜度也是 O(NlogN)