功能描述
對(duì)于一個(gè)長(zhǎng)度為N數(shù)組array
- 在
的時(shí)間復(fù)雜度下，統(tǒng)計(jì)出從第一個(gè)元素開(kāi)始區(qū)間和，也就是
，
- 給數(shù)組中一個(gè)元素增加一個(gè)值
老厌，時(shí)間復(fù)雜度
- 空間復(fù)雜度
- 實(shí)現(xiàn)特別簡(jiǎn)單
注意事項(xiàng)
- 沒(méi)有辦法直接算出區(qū)間和，需要通過(guò)換算
, 時(shí)間復(fù)雜度還是
- 方便直接給位置增加一個(gè)特定值黎炉，但是修改查詢(xún)單個(gè)數(shù)值比較復(fù)雜枝秤。
- 無(wú)法區(qū)間修改，不能實(shí)現(xiàn)線段樹(shù)的RMQ功能
- 區(qū)間和的時(shí)間復(fù)雜度比傳統(tǒng)線段樹(shù)要低慷嗜，實(shí)現(xiàn)更加簡(jiǎn)單
- 效率和zkw線段樹(shù)差不多淀弹，所以現(xiàn)在這個(gè)算法使用很少了
算法的結(jié)構(gòu)
image.png
函數(shù)lowbit在樹(shù)狀數(shù)組中操作的說(shuō)明
lowbit函數(shù)的作用是找到數(shù)字二進(jìn)制的最后一個(gè)數(shù)字1。舉例
| 5 | 101 | 1 | 1 |
| 6 | 110 | 10 | 2 |
| 10 | 1010 | 10 | 2 |
| 20 | 10100 | 100 | 4 |
| 22 | 10110 | 10 | 2 |
| 27 | 11011 | 1 | 1 |
路徑圖
加上lowbit數(shù)值 的作用庆械，是找到最近的父親節(jié)點(diǎn)薇溃。在修改點(diǎn) 的數(shù)值是，父親的尋找過(guò)程是：
- 第一個(gè)父親的下標(biāo)是是
- 第二個(gè)父親是下標(biāo)是
- 第三個(gè)父親的下標(biāo)（如果有）是
- 直到計(jì)算出來(lái)的下標(biāo)缭乘，超過(guò)了數(shù)組的范圍痊焊，就計(jì)算完成了。
減去lowbit的數(shù)值的作用忿峻，是找到每一個(gè)需要被統(tǒng)計(jì)的子樹(shù)的根節(jié)點(diǎn)薄啥。 是上圖紅色標(biāo)志的路線。對(duì)于的數(shù)值逛尚，分別有三個(gè)子樹(shù)需要被計(jì)算進(jìn)來(lái)
- 第一個(gè)需要收集的子樹(shù)是 sum( 11, 11 ) , 因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=lowbit(11_%7B10%7D)%3D%20lowbit(%201011_2%20)%20%3D%201_2" alt="lowbit(11_{10})= lowbit( 1011_2 ) = 1_2" mathimg="1">垄惧， 這個(gè)子樹(shù)只有一個(gè)數(shù)，就是
- 第二個(gè)需要收集的子樹(shù)覆蓋寬度绰寞，是
, 也就是到逊，有兩個(gè)元素，也就是
- 以此類(lèi)推滤钱， 第三個(gè)子樹(shù)是
觉壶。 這時(shí)候統(tǒng)計(jì)完畢，
示范代碼
C語(yǔ)言實(shí)現(xiàn)件缸，來(lái)自維基百科铜靶。但是這里我修改了一點(diǎn)點(diǎn)，size放大了1他炊， 更方便理解争剿。數(shù)值的存儲(chǔ)是
#define LSB(i) ((i) & -(i)) // zeroes all the bits except the least significant one
int A[SIZE+1];
int sum(int i) // Returns the sum from index 1 to i
{
int sum = 0;
while (i > 0)
sum += A[i], i -= LSB(i);
return sum;
}
void add(int i, int k) // Adds k to element with index i
{
while (i <=SIZE)
A[i] += k, i += LSB(i);
}
題目
leetcode 的 683 - k-empty-slots可以使用樹(shù)狀數(shù)組實(shí)現(xiàn)
