樹狀數(shù)組

前置知識 :

差分&前綴和
位運算
樹的基本概念和定理

1. 什么是樹狀數(shù)組?

樹狀數(shù)組(Binary Indexed Tree(B.I.T), Fenwick Tree)是一個查詢和修改復(fù)雜度都為Log(N)的數(shù)據(jù)結(jié)構(gòu)。主要用于查詢?nèi)我鈨晌恢g的所有元素之和，但是每次只能修改一個元素的值；經(jīng)過簡單修改可以在Log(N)的復(fù)雜度下進行范圍修改，但是這時只能查詢其中一個元素的值(如果加入多個輔助數(shù)組則可以實現(xiàn)區(qū)間修改與區(qū)間查詢)?！俣劝倏?/p>

~~SMG~~

其實基本的樹狀數(shù)組就是實現(xiàn)這樣一個問題

——求

數(shù)組中一段區(qū)間的和
修改數(shù)組中某一個數(shù)

小明:"不就是前綴和可以搞定的嘛!"

$\large\texttt{嗖---}$

#include<iostream>
using namespace std;
int a[1000000];
int sum[1000000];
int main()
{
    int n, ask;
    cin >> n >> ask;
    while (ask --)
    {
        char type;
        cin >> type;
        if (type == 'A') //查詢
        {
            int x;
            cin >> x;
            cout << sum[x] << endl;
        }
        else if (type == 'B') //修改
        {
            int x, p;
            cin >> x >> p;
            for (int i = x; i <= n; i ++) sum[i] += p;
        }
    }
    return 0;
}

$\large\texttt{提交}$

image

跑得好快呀!

那么這時我們的樹狀數(shù)組就該出場啦~

首先,樹狀數(shù)組,顧名思義長得像樹的數(shù)組

所以樹狀數(shù)組長這個樣

image

上面是樹,下面是數(shù)組

首先是求區(qū)間和

通過這幅圖,應(yīng)該不難看出,一個數(shù)到最前面的距離就等于剛好包含這個區(qū)間的幾個橫條的和:

比如區(qū)間1~7為:

image

綠色條的和

知道這個,那么任意兩個數(shù)之間的區(qū)間也就容易了,
只需要把兩個區(qū)間到1的區(qū)間和相減就可以了。

那有了區(qū)間和還不夠,還要修改呢

修改也簡單,只需要每次修改包含自己的橫條就好了(廢話)

比如修改5的值:

image

把藍色橫條全改了就好啦!

這么說兩個功能都準(zhǔn)備好了,那就到代碼實現(xiàn)了

首先引入一個概念——Lowbit

指一個數(shù)在二進制下最末尾的1所對應(yīng)的值

十進制數(shù)	二進制數(shù)	Lowbit值
1	$\large\texttt{1}$	1
2	$\large\texttt{1}$ 0	2
3	1 $\large\texttt{1}$	1
4	$\large\texttt{1}$ 00	4
5	10 $\large\texttt{1}$	1
6	1 $\large\texttt{1}$ 0	2
7	11 $\large\texttt{1}$	1
8	$\large\texttt{1}$ 000	8
9	100 $\large\texttt{1}$	1
10	10 $\large\texttt{1}$ 0	2
...	...	...

發(fā)現(xiàn)了嗎,跟它在樹狀數(shù)組中的高度是一模一樣的

image

首先二進制負數(shù)就是原數(shù)的反碼(把原數(shù)的0變?yōu)?,1變?yōu)?)+1(也稱原數(shù)的補碼)

也就是說我們用原數(shù)按位與(&)原數(shù)的補碼

就是最后一個1的位置所表示的值,也就是Lowbit值

綜上,Lowbit(x) = x&(-x)

如果沒看懂也不要緊,記下來就好了。

根據(jù)上面的結(jié)論,我們可以搞定兩個東西

1. 一個位置左邊的橫條在 x - Lowbit(x)

2. 一個位置上面的橫條在 x + Lowbit(x)

(隨便找一個點在上圖中康康就知道啦)

有了這幾個結(jié)論,我們就可以開始搞事情了

首先是區(qū)間查詢

只需要一直往左邊找。(上面的1號結(jié)論)

代碼很簡單:

// tree表示橫條的值
int get_sum(int x) // 求前x個數(shù)的和
{
    int sum = 0;
    while (x > 0)
    {
        ans += tree[x]; // 加上當(dāng)前點的值
        x -= lowbit(x); // 繼續(xù)找左邊的一個橫條
    }
    return ans;
}

接著是修改點的值

只需要一直找上一個橫條。(上面的2號結(jié)論)

代碼:

// 這個是加一個數(shù),可以有別的修改
void add(int x, int p)
{
    while (x <= n)
    {
        tree[x] += p; //修改改當(dāng)前點
        x += lowbit(x); // 繼續(xù)找上面的橫條
    }
}