之前分享了《樹狀數組模板》和《離散化模板》，今天來看幾道練習題。
二、區域和檢索 - 數組可修改題意：給一個數組，有兩個操作。
1）求區間[l,r]的和。
2）修改下標 i 的值為v。
思路：題意是單點更新，求區間和。
赤裸裸的樹狀數組模板題，直接套用即可。
代碼：
https://github.com/tiankonguse/leetcode-solutions/blob/master/problemset-new/003/00307-range-sum-query-mutable/range-sum-query-mutable.cc
三、計算右側小於當前元素的個數題意：給一個數組，求每個位置右側比自己小的元素個數。
思路：如果不看數據範圍的話，裸套樹狀數組模板即可。
具體細節是從後到前遍歷，先通過前綴和求出小於自己的元素個數，然後把自己再加入到樹狀數組中。
這道題的元素值很大，所以需要使用離散化模板進行重新標號。
代碼：
https://github.com/tiankonguse/leetcode-solutions/blob/master/problemset-new/003/00315-count-of-smaller-numbers-after-self/count-of-smaller-numbers-after-self.cc
四、翻轉對題意：給一個數組，求每個元素左側大於兩倍當前值的元素個數。
使用數學公式就是，求 i<j 且num[i] > num[j]*2 的個數。
思路：與上一題類似，只是大小關係只是變成了兩倍。
求大於當前值的個數，其實就是求後綴和了。
所以只需要使用 Upper 算法找到第一個大於兩倍值的下標，然後求後綴和即可。
代碼：
https://github.com/tiankonguse/leetcode-solutions/blob/master/problemset-new/004/00493-reverse-pairs/reverse-pairs.cc
五、區間和的個數題意：給一個數組，問區間和在[lower, upper]範圍內的區間個數。
思路：暴力是O(n^2)的複雜度，我們需要想出一個更快的算法來。
我們可以思考這樣一個情況。
從左到右掃描數組的時候，假設當前位置是j。
如果我們能快速找到以j為後綴的滿足要求的區間，那就可以快速找到答案了。
再進一步假設。
假設我們已經有所有以j為後綴的區間和了，儲存在樹狀數組裡。
sum[1 , j]
...
sum[j-2, j]
sum[j-1, j]
sum[j , j]
那就可以log(n)的複雜度來查詢後綴和在區間[l, r]的個數了。
那如何由第j個元素的後綴和轉化為第j+1個元素的後綴和呢？
j的所有後綴和加上nums[j+1]，就幾乎都是j+1的所有後綴和了。
sum[1 , j] + nums[j+1]
...
sum[j-2, j] + nums[j+1]
sum[j-1, j] + nums[j+1]
sum[j , j] + nums[j+1]
nums[j+1]
上面的話聚合在一起就是求 j的所有後綴和 加上 num[j+1] 後，值在範圍 [l, r]內的個數。
那反過來，根據小學二年級學的一個性質，兩邊同時減去一個數字，答案不變。
所以 區間[l, r] 和 j的所有後綴和可以都減去nums[j+1]。
問題就轉化為了所有 j的後綴和滿足區間 [l-nums[j+1], r-nums[j+1]]的個數。
到這裡，不知道你是否還明白在說什麼。
簡單的說，我們通過修改區間[l, r]就可以將j+1的後綴和問題轉化為j的後綴和問題。
這裡唯一需要注意的就是，最後一個元素nums[j+1]不是j的後綴和，所以沒辦法直接減去nums[j+1]。
所以這裡需要通過原始的[l,r]與 j的區間進行偏移修正，將nums[j+1]轉化為j的後綴和形式。
修正的值其實也很容易計算。
通過j到j+1的關係，可以發現修正一次的偏移量是nums[j+1]。
那麼j到j+2修正偏移量就nums[j+1] + nums[j+2]了。
提取規律，第k個值需要修正的偏移量就是前綴和sum[1, k]了。
代碼：
https://github.com/tiankonguse/leetcode-solutions/blob/master/problemset-new/003/00327-count-of-range-sum/count-of-range-sum.cc
六、最後這四道樹狀數組的題都很有特徵。
第一道是裸套模板。
第二道是稍微變通一下來套模版。
第三道則存在非離散化的數據，需要使用Upper或者Lower來查找第一個滿足情況的下標。
第四道題則屬於最難的，需要反向修改查詢的區間，這種思路可以學習一下，是個不錯的思路。
加油，算法人。
《完》
-EOF-
題圖：來自朋友圈。
上篇文章： 必備算法模版之大數據離散化
推薦：必備算法模版之樹狀數組
長按二維碼，一起成長學習
▲ 長按關注，天天成長
覺得有幫助可以點擊好看與轉發，謝謝！