vector<int> nums = {1, 5, -2, 7, 4, 3, 6, 2};
如果要求 range sum,例如 sum(1, 5) = 17
有兩種operation,1. 求某個range的和,2. update每個一值。
如果使用vector,和prefix sum,分別的time complexity如下:
update | getSum | |
---|---|---|
vector | ||
prefix-sum |
如果是update非常頻繁,但是求和的情況非常少,可以使用vector。
相反的,
如果是update很少,但是求和的情況非常頻繁,就可以使用prefix-sum。
如果是update和求和都很頻繁,那就必須要用binary index tree,
update | getSum | |
---|---|---|
BIT |
使用N-ary tree,parent和child只相差一個bit。
使用dummy node(index 0),不儲存任何資料
child存放的數值,是到parent的總和(不包括parent)。例如: index-12 = nums[9] + nums[10] + nums[11] + nums[12]。
getSum(index),計算從0 ~ index的總和。就是從一路從index加到root。例如: sum(0 ~ 13) = bit(13) + bit(12) + bit(8);
因為是tree的走訪,所以time complexity =
從BIT中計算0 ~ index的總和。
更新某個vector中的數值,因為n[i]已經加起來了,所以只能增減n[i]的數值。
從一個vector<int> nums建立一個BIT。
ref : Fenwick Tree/Binary Indexed Tree (BIT)
和1D BIT一樣,使用長寬都大1的2D vector來儲存。
update function
calculate range sum function
BIT可以用來計算range sum,如果反過來使用把數值當成index, value改為個數,則可計算比目前數值大或小的個數。
例如315. Count of Smaller Numbers After Self
nums = [5,2,6,1]
因為0為dummy node,所以index = nums[i] + 1
當idx = 0, nums[0] = 5, index = 5 + 1 = 6往右看如下
index | 0 | 1 | 2 | 3 | 4 | 5 | 6★ | 7 |
---|---|---|---|---|---|---|---|---|
value | 1 | 1 | 1 |
則range sum(1, 5)即為小於nums[0] = 5的個數。
題目很明顯就是要實現Binary index tree。
給你一個vector<int> nums, 回傳右邊比目前的數還小的個數。
- 使用BIT來計算比目前的數還小的個數。
leetcode
刷題