題目: 327. Count of Range Sum
難度: Hard
目前下列解法的時間複雜度: O(n*lg(n))
題目說明
給你 n 一條整數陣列(有正有負)，及兩個數字當上下界。
求符合下列的區間數:
該區間的區間和介於上下界之間(都包含)。
解法: 用查詢區間操作很快的東東，例如 fake segment tree, fenwick tree
想法一步一步來。
首先，釐清最原始的暴力搜尋大概長成怎樣:
界定區間端點，每次從某一端一路加到另一端，在區間內則答案+1。
此方法 O(n**3) 。
接著一路加過去可以用前綴和，尾端減頭端。
於是時間複雜度變成 O(n**2) 。
還是TLE。
再來，再看一次需求：數量。
於是一路撸過去的過程中，記好之前看過那些前綴和，並且他們有排序好。
答案+1的條件是: "下界 <= 現在的前綴和 - 之前某個前綴和 <= 上界"
移項: "之前某個前綴和 <= 現在的前綴和 - 下界" 與 "現在的前綴和 - 上界 <= 之前某個前綴和"
所以可以對上下界二分搜，進而取得數量。
那麼怎麼樣在看過前綴和後，可以很快地加入排序記好數量呢: 平衡樹(需有記錄子樹大小)、fake segment tree(區間查詢+單點修改)、fenwick tree(加法區間查詢+單點修改)、這個(但leetcode不能用)
平衡樹大概很直觀。某上下界範圍內節點數查詢，直接就有數量，故不多做說明。主要還是因為我不是用這種寫法
fake segment tree 和 fenwick tree 功能類似，但 fenwick tree 限定在有反運算子 (inverse operator) 才能用，除非查詢都是 0~n ； fenwick tree 不需額外記憶體，他直接對原本的資料修改。
難度: Hard
目前下列解法的時間複雜度: O(n*lg(n))
題目說明
給你 n 一條整數陣列(有正有負)，及兩個數字當上下界。
求符合下列的區間數:
該區間的區間和介於上下界之間(都包含)。
解法: 用查詢區間操作很快的東東，例如 fake segment tree, fenwick tree
想法一步一步來。
首先，釐清最原始的暴力搜尋大概長成怎樣:
界定區間端點，每次從某一端一路加到另一端，在區間內則答案+1。
此方法 O(n**3) 。
接著一路加過去可以用前綴和，尾端減頭端。
於是時間複雜度變成 O(n**2) 。
還是TLE。
再來，再看一次需求：數量。
於是一路撸過去的過程中，記好之前看過那些前綴和，並且他們有排序好。
答案+1的條件是: "下界 <= 現在的前綴和 - 之前某個前綴和 <= 上界"
移項: "之前某個前綴和 <= 現在的前綴和 - 下界" 與 "現在的前綴和 - 上界 <= 之前某個前綴和"
所以可以對上下界二分搜，進而取得數量。
那麼怎麼樣在看過前綴和後，可以很快地加入排序記好數量呢: 平衡樹(需有記錄子樹大小)、fake segment tree(區間查詢+單點修改)、fenwick tree(加法區間查詢+單點修改)、這個(但leetcode不能用)
平衡樹大概很直觀。某上下界範圍內節點數查詢，直接就有數量，故不多做說明。
fake segment tree 和 fenwick tree 功能類似，但 fenwick tree 限定在有反運算子 (inverse operator) 才能用，除非查詢都是 0~n ； fenwick tree 不需額外記憶體，他直接對原本的資料修改。
程式碼以 fake segment tree 為主。因為懶得再寫 而且比較泛用，這樣copy-paste的機會比較多
首先算好前綴和
然後另外蒐集起來排序，當查索引用(用二分搜)
然後你知道的: 用查到的上下界索引問 fake segment tree 你有多少，並更新答案；用查到的現在前綴和的索引對 fake segment tree +1
從一開始的前綴一路撸到底就做完囉。
source code
fake segment tree可以看
這篇
和
這篇
或自行找英文材料
首先算好前綴和
然後另外蒐集起來排序，當查索引用(用二分搜)
然後你知道的: 用查到的上下界索引問 fake segment tree 你有多少，並更新答案；用查到的現在前綴和的索引對 fake segment tree +1
從一開始的前綴一路撸到底就做完囉。
source code
fake segment tree可以看
這篇
和
這篇
或自行找英文材料
