C語(yǔ)言詳細(xì)講解樹(shù)狀數(shù)組與線段樹(shù)

更新時(shí)間：2022年04月12日 15:50:28 作者：小羊努力變強(qiáng)

顧名思義，樹(shù)狀數(shù)組就是用數(shù)組來(lái)模擬樹(shù)形結(jié)構(gòu)唄。那么衍生出一個(gè)問(wèn)題，為什么不直接建樹(shù)，因?yàn)闃?shù)狀數(shù)組能處理的問(wèn)題就沒(méi)必要建樹(shù)。線段樹(shù)是一種二叉搜索樹(shù)，與區(qū)間樹(shù)相似，它將一個(gè)區(qū)間劃分成一些單元區(qū)間，每個(gè)單元區(qū)間對(duì)應(yīng)線段樹(shù)中的一個(gè)葉結(jié)點(diǎn)

樹(shù)狀數(shù)組

動(dòng)態(tài)求連續(xù)區(qū)間和

給定 n 個(gè)數(shù)組成的一個(gè)數(shù)列，規(guī)定有兩種操作，一是修改某個(gè)元素，二是求子數(shù)列 [a,b] 的連續(xù)和。

輸入格式
第一行包含兩個(gè)整數(shù) n 和 m，分別表示數(shù)的個(gè)數(shù)和操作次數(shù)。

第二行包含 n 個(gè)整數(shù)，表示完整數(shù)列。

接下來(lái) m 行，每行包含三個(gè)整數(shù) k,a,b （k=0，表示求子數(shù)列[a,b]的和；k=1，表示第 a 個(gè)數(shù)加 b）。

數(shù)列從 1 開(kāi)始計(jì)數(shù)。

輸出格式
輸出若干行數(shù)字，表示 k=0 時(shí)，對(duì)應(yīng)的子數(shù)列 [a,b] 的連續(xù)和。

數(shù)據(jù)范圍
1≤n≤100000,
1≤m≤100000，
1≤a≤b≤n,
數(shù)據(jù)保證在任何時(shí)候，數(shù)列中所有元素之和均在 int 范圍內(nèi)。

輸入樣例：

10 5
1 2 3 4 5 6 7 8 9 10
1 1 5
0 1 3
0 4 8
1 7 5
0 4 8

輸出樣例：

11
30
35

這道題我最開(kāi)始的想法就是只用前綴和，但后來(lái)發(fā)現(xiàn)只用前綴和會(huì)超時(shí)，因?yàn)閿?shù)據(jù)范圍

1≤n≤100000,

1≤m≤100000，

1≤a≤b≤n

//前綴和會(huì)超時(shí)
#include<bits/stdc++.h>

using namespace std;

const int N = 1000010;

int n,m;
int s1[N],s2[N];

int main ()
{
    cin >> n >> m;
    for(int i = 1 ; i <=n ; i++)
    {
        cin >> s1[i];
        s2[i] = s2[i-1] + s1[i];
    }
    while(m--)
    {
        int k , a , b;
        cin >> k >> a >> b;
        if(k == 1)
        {
            s1[a] +=  b;
            for(int i = 1 ; i <= n ; i++)
            {
                s2[i] = s2[i-1] + s1[i];
            }
        }
        if(k == 0)
        {
            
                printf("%d\n", s2[b] - s2[a-1]);
            
        }
    }
}

然后我們?cè)賮?lái)分析一下樹(shù)狀數(shù)組是怎樣的。

在這里插入圖片描述

1、lowbit(x):返回x的最后一位1

2、add(x,v):在x位置加上v，并將后面相關(guān)聯(lián)的位置也加上v

3、query(x):詢問(wèn)x的前綴和

時(shí)間復(fù)雜度 O(logn)

假設(shè)原序列為a，樹(shù)狀數(shù)組序列為c,那么是怎么由原序列得到樹(shù)狀數(shù)組序列的呢？(可以把c理解為a的前綴和序列，只是前綴和關(guān)系不像一般前綴和那樣簡(jiǎn)單、線性)
1. 首先，將一維的樹(shù)狀數(shù)組序列c看成多層的序列，c[i]屬于第幾層，取決于i的二進(jìn)制表示中最后一個(gè)1后面有幾個(gè)0，有幾個(gè)0就在第幾層，顯而易見(jiàn),當(dāng)i為奇數(shù)時(shí)，c[i]是在第0層的
因?yàn)閘owbit(x)=2^k,k表示x的二進(jìn)制表示后面有多少個(gè)0
（lowbit(n)求得n的二進(jìn)制表示中最后一個(gè)1以及往后的0）
可以得到關(guān)系：
c[x]=a[x−lowbit(x),x]
此關(guān)系描述了序列cc中每個(gè)元素是哪一段序列a中元素的和
2. 如何通過(guò)樹(shù)狀數(shù)組求前綴和？
由上面公式知道，想要求序列aa中11到xx的和，則應(yīng)該是：

在這里插入圖片描述

因而可得代碼：

int res=0;
for(int i=x;i>0;i-=lowbit(x)) res+=c[i];
return res;

如何通過(guò)樹(shù)狀數(shù)組進(jìn)行單點(diǎn)修改？

這里我們給出一個(gè)結(jié)論：一個(gè)結(jié)點(diǎn)a[i]或c[i]的父結(jié)點(diǎn)為c[i+lowbit(i)]

所以當(dāng)我們改變a[i]的值時(shí)，依次遞歸向上更新父結(jié)點(diǎn)的值即可。

代碼：

a[x]+=v;
for(int i=x;i<=n;i+=lowbit(i)) c[i]+=v;

最終代碼：

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int n, m;
int a[N], tr[N];//tr[N]表示圖中的c[N];

int lowbit(int x)
{
    return x & -x;
}

void add(int x, int v)
{
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += v;
}

int query(int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i ++ ) add(i, a[i]);

    while (m -- )
    {
        int k, x, y;
        scanf("%d%d%d", &k, &x, &y);
        if (k == 0) printf("%d\n", query(y) - query(x - 1));
        else add(x, y);
    }

    return 0;
}

最后再對(duì)比一下一般前綴和和樹(shù)狀數(shù)組：

在這里插入圖片描述

可以看出在修改和查詢操作占比差不多時(shí)，樹(shù)狀數(shù)組的效率更高

那么什么時(shí)候用樹(shù)狀數(shù)組，什么時(shí)候用一般前綴和算法呢？

這就要明白這兩個(gè)算法的本質(zhì)區(qū)別：

一般前綴和算法是離線算法，它不支持動(dòng)態(tài)的改變單個(gè)元素的值，或者說(shuō)改變單個(gè)元素值后，重新維護(hù)前綴和所花費(fèi)的代價(jià)很大。

樹(shù)狀數(shù)組是在線算法，支持動(dòng)態(tài)改變單個(gè)元素的值，以很小的代價(jià)動(dòng)態(tài)維護(hù)前綴和。

所以當(dāng)僅僅需要用到前綴和，不涉及動(dòng)態(tài)的改變單個(gè)元素的值時(shí)，首選一般前綴和算法，否則就用樹(shù)狀數(shù)組。

數(shù)星星

天空中有一些星星，這些星星都在不同的位置，每個(gè)星星有個(gè)坐標(biāo)。

如果一個(gè)星星的左下方（包含正左和正下）有 k 顆星星，就說(shuō)這顆星星是 k 級(jí)的。

例如，上圖中星星 5 是 3 級(jí)的（1,2,4 在它左下），星星 2,4 是 1 級(jí)的。

例圖中有 1 個(gè) 0 級(jí)，2 個(gè) 1 級(jí)，1 個(gè) 2 級(jí)，1 個(gè) 3 級(jí)的星星。

給定星星的位置，輸出各級(jí)星星的數(shù)目。

換句話說(shuō)，給定 N 個(gè)點(diǎn)，定義每個(gè)點(diǎn)的等級(jí)是在該點(diǎn)左下方（含正左、正下）的點(diǎn)的數(shù)目，試統(tǒng)計(jì)每個(gè)等級(jí)有多少個(gè)點(diǎn)。

輸入格式
第一行一個(gè)整數(shù) N，表示星星的數(shù)目；

接下來(lái) N 行給出每顆星星的坐標(biāo)，坐標(biāo)用兩個(gè)整數(shù) x,y 表示；

不會(huì)有星星重疊。星星按 y 坐標(biāo)增序給出，y 坐標(biāo)相同的按 x 坐標(biāo)增序給出。

輸出格式
N 行，每行一個(gè)整數(shù)，分別是 0 級(jí)，1 級(jí)，2 級(jí)，……，N−1 級(jí)的星星的數(shù)目。

數(shù)據(jù)范圍
1≤N≤15000,
0≤x,y≤32000

輸入樣例：

5
1 1
5 1
7 1
3 3
5 5

輸出樣例：

1
2
1
1
0

這題看起來(lái)是二維的，但是實(shí)際上我們可以不用考慮y，因?yàn)樾切前?y 坐標(biāo)增序給出，y 坐標(biāo)相同的按 x 坐標(biāo)增序給出，所以我們只需要實(shí)時(shí)更新一下我們的樹(shù)狀數(shù)組就可以了。

如何更新？

這個(gè)題目本身就是一道利用前綴和思想做的題目。就和開(kāi)頭所說(shuō)過(guò)的一樣，只要求出有多少個(gè)星星的 x 值不小于該星星的 x 值就可以了，而這個(gè)過(guò)程就是利用的前綴和。

那讓我們先用前綴和的思想來(lái)看一下這道題目。

假設(shè)現(xiàn)在存在一個(gè)前綴和數(shù)組 sum ，那么每當(dāng)我們輸入一個(gè) x 的時(shí)候，我們都需要把 x 后面（包含x）的所有前綴和都加上 1 ，(因?yàn)樵?x 后面的數(shù)都比 x 大，所以需要更新后面所有的前綴和)。然后我們?cè)诿看屋斎?x 的時(shí)候都實(shí)時(shí)更新一下前綴和并且實(shí)時(shí)計(jì)算一下我們的星星的等級(jí)就可以了。

這里為什么要強(qiáng)調(diào)實(shí)時(shí)計(jì)算星星等級(jí)的值呢？

因?yàn)槲覀冞@種操作方法是忽略了 y 的，之所以可以忽略 y 是因?yàn)轭}目輸入的原因，所以其實(shí)我們是利用了這一特性來(lái)簡(jiǎn)化我們的算法的。其實(shí)如果這道題目輸入的 y 并不按照不降原則來(lái)輸入的話，那么這種算法就不對(duì)了。

現(xiàn)在說(shuō)明一下為什么要實(shí)時(shí)計(jì)算，因?yàn)楹竺孑斎氲?x 值很可能比我們前面輸入的 x 值要小，因?yàn)閿?shù)據(jù)輸入的是按y不降輸入的，而 x 可以是任意的，如果我們不實(shí)時(shí)計(jì)算，而是等到全部處理完再計(jì)算的話，會(huì)導(dǎo)致 “x 雖然比你大但是 y 比你小的情況”，而這種情況是顯然不符合我們的題意的，所以說(shuō)我們這種利用前綴和的算法是很特殊的，是僅僅針對(duì)于這個(gè)題目的。

能用到數(shù)據(jù)結(jié)構(gòu)的算法的題目，往往是根據(jù)數(shù)據(jù)結(jié)構(gòu)的特性來(lái)決定的。比如這個(gè)題目我們?yōu)槭裁匆脴?shù)狀數(shù)組來(lái)處理？是因?yàn)槲覀冞@里要運(yùn)用前綴和，以及更新前綴和，而這恰好符合樹(shù)狀數(shù)組的特性，所以我們利用了它。

所以本題的思考思路總結(jié)應(yīng)該是：

1、分析題目，通過(guò)輸入特性判斷解題方法

2、想想暴力解法怎么做？利用前綴和，每次用O(n)的時(shí)間復(fù)雜度更新前綴和

3、想想是否能優(yōu)化？

4、想到樹(shù)狀數(shù)組優(yōu)化

5、利用樹(shù)狀數(shù)組解決題目

請(qǐng)看代碼：

#include <bits/stdc++.h>

using namespace std;

const int N = 32010;

int n;
int tr[N], level[N];

int lowbit(int x)
{
    return x & -x;
}

void add(int x)
{
    for (int i = x; i < N; i += lowbit(i)) tr[i] ++ ;
}

int sum(int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
    {
        int x, y;
        scanf("%d%d", &x, &y);
        x ++ ;
        level[sum(x)] ++ ;
        add(x);
    }

    for (int i = 0; i < n; i ++ ) printf("%d\n", level[i]);

    return 0;
}

線段樹(shù)

動(dòng)態(tài)求連續(xù)區(qū)間和

我們還是以動(dòng)態(tài)求連續(xù)區(qū)間和為例

線段樹(shù)基于分治思想

那么我們可以把每一個(gè)區(qū)間一分為二，這樣就把整個(gè)區(qū)間變成了一棵樹(shù)。

這樣的話我們可以看一下兩個(gè)操作，因?yàn)槭菢?shù)上，而且是一棵滿二叉樹(shù)，所以深度一定是O(logN)的。

在這里插入圖片描述

1、pushup(u):用子節(jié)點(diǎn)信息來(lái)更新當(dāng)前節(jié)點(diǎn)信息（把信息往上傳遞）

2、build(u,l,r):在一段區(qū)間上初始化線段樹(shù)，其中u表示根結(jié)點(diǎn)，l表示左邊界，r表示右邊界

3、query(u,l,r):查詢某段區(qū)間的和，其中u表示根結(jié)點(diǎn)，l表示左邊界，r表示右邊界

4、modify(u,x,v):修改操作，在u結(jié)點(diǎn)中，x位置加上v

我們來(lái)看一些基本的操作吧！

首先是上傳的操作，線段樹(shù)的意思就是用左右子樹(shù)更新根節(jié)點(diǎn)。

怎么寫呢？

這個(gè)的話我們結(jié)合著拿到題寫吧。

就是單點(diǎn)修改，區(qū)間查詢。

線段樹(shù)的話一般使用結(jié)構(gòu)體維護(hù)。

結(jié)構(gòu)體里想要啥有啥放進(jìn)去就行了。

struct Node
{
    int l, r;//左右端點(diǎn)區(qū)域

    int sum;//各種查詢變量存儲(chǔ)區(qū)域

    //最后還有個(gè)懶標(biāo)記區(qū)域，一般在區(qū)間修改時(shí)使用。
}tr[N * 4];//4倍空間

那么的話pushup的操作就是用左右兩邊的區(qū)間更新總區(qū)間。

這個(gè)的話很簡(jiǎn)單，大區(qū)間等于小區(qū)間的和。

void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

然后就是建樹(shù)操作，在最開(kāi)始需要把樹(shù)“建造出來(lái)”。

這個(gè)可以直接遞歸建立樹(shù)。

這個(gè)的話可以分治處理。

void build(int u, int l, int r)
{
    if (l == r) tr[u] = {l, r, w[r]};
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

然后就是變化操作和查詢操作。

變化操作就是直接搜就行了。

void modify(int u, int x, int v)
{
    if (tr[u].l == x && tr[u].r == x) tr[u] = {x, x, v;
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
}

然后是查詢操作。

這個(gè)也不難。

就可以直接判斷區(qū)間。

int query(int u, int l, int r)
{
    if(tr[u].l >= l && tr[u].r <= r) return tr[u].v;
    int mid = tr[u].l + tr[u].r >> 1;
    int v = 0;
    if(l <= mid) v = query(u << 1, l, r);
    if(r > mid) v = max(v, query(u << 1 | 1, l, r));
    return v;
}

線段樹(shù)的思想上面已經(jīng)說(shuō)完了，那么就是代碼了：

#include<bits/stdc++.h>

using namespace std;

const int N = 100010;

int n, m;
int w[N];

struct Node
{
    int l, r;
    int sum;
}tr[N * 4];

void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void build(int u, int l, int r)
{
    if(l == r) tr[u] = {l, r, w[r]};
    else
    {
        tr[u] = {l, r};
        int mid = (l + r) >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void change(int u, int x, int v)
{
    if(tr[u].l == x && tr[u].r == x) 
    {
        tr[u] = {x, x, tr[u].sum + v};
    }
    else
    {
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(x <= mid) change(u << 1, x, v);
        else change(u << 1 | 1, x, v);
        pushup(u);
    }
}

int query(int u, int l, int r)
{
    if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
    else
    {
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(r <= mid) return query(u << 1, l, r);
        else if(l > mid) return query(u << 1 | 1, l, r);
        else
        {
            int left = query(u << 1, l, r);
            int right = query(u << 1 | 1, l, r);
            int ans;
            ans = left + right;
            return ans;
        }

    }
} 

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        cin >> w[i];
    }
    build(1, 1, n);
    while(m --)
    {
        int op, l, r;
        cin >> op >> l >> r;
        if(op == 0)
        {
            cout << query(1, l, r) << endl;
        }
        else
        {
            change(1, l, r);
        }
    }
    return 0;
}

數(shù)列區(qū)間最大值

輸入一串?dāng)?shù)字，給你 M 個(gè)詢問(wèn)，每次詢問(wèn)就給你兩個(gè)數(shù)字 X,Y，要求你說(shuō)出 X 到 Y 這段區(qū)間內(nèi)的最大數(shù)。

輸入格式
第一行兩個(gè)整數(shù) N,M 表示數(shù)字的個(gè)數(shù)和要詢問(wèn)的次數(shù)；

接下來(lái)一行為 N 個(gè)數(shù)；

接下來(lái) M 行，每行都有兩個(gè)整數(shù) X,Y。

輸出格式
輸出共 M 行，每行輸出一個(gè)數(shù)。

數(shù)據(jù)范圍
1≤N≤105,
1≤M≤106,
1≤X≤Y≤N,
數(shù)列中的數(shù)字均不超過(guò)231−1

輸入樣例：

10 2
3 2 4 5 6 8 1 2 9 7
1 4
3 8

輸出樣例：

5
8

這題和動(dòng)態(tài)求連續(xù)區(qū)間和差不多，直接套就可以了。

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;
int w[N];//數(shù)值

struct Node
{
    int l,r,maxv;// 把記錄區(qū)間和的sum換成了記錄區(qū)間最大值的maxv
}tr[4*N];//二叉樹(shù) n+n/2+n/4..=2n 加底層最大 =4n

int pushup(int u)
{
    return tr[u].maxv = max (tr[u<<1].maxv,tr[u<<1|1].maxv);//更新數(shù)據(jù) 兩個(gè)子樹(shù)當(dāng)中取最大
}

void build(int u,int l,int r)//初始化線段樹(shù) u序號(hào) lr具體范圍
{
    if(l==r)tr[u]={l,r,w[r]};//如果只有一個(gè)數(shù)據(jù) 即最大是當(dāng)前數(shù)據(jù)
    else 
        {
            tr[u]={l,r};
            int mid=l+r>>1;//初始化二叉樹(shù) 只與結(jié)構(gòu)有關(guān) 與本身數(shù)據(jù)無(wú)關(guān) 所以mid = l+r>>1
            build(u<<1,l,mid),build(u<<1|1,mid+1,r);//遞歸找兩個(gè)子樹(shù)
            pushup(u);//當(dāng)前的最大值等于兩個(gè)子樹(shù)間的最大值
        }
}

int query(int u,int l,int r)//u序號(hào) lr要查找的范圍
{
    if(l<=tr[u].l&&tr[u].r<=r)return tr[u].maxv;//如果要查找的范圍包含當(dāng)前范圍則直接返回最值
    else 
        {
            int maxv=0;
            int mid=tr[u].l+tr[u].r>>1;//與本身數(shù)據(jù)有關(guān) 做中間值 用于找包含部分
            if(l<=mid)maxv=query(u<<1,l,r);//如果左邊有包含部分 則更新左子樹(shù)
            if(r>=mid+1)maxv=max(maxv,query(u<<1|1,l,r));//如果右邊有包含部分 則更新右子樹(shù)
            return maxv;//當(dāng)前maxv實(shí)際是由底層逐層比對(duì)返回的在指定區(qū)域內(nèi)的最大值
        }
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++)scanf("%d",&w[i]);

    build(1,1,n);//初始化線段樹(shù)

    int x,y;
    while(m--)
        {
            scanf("%d%d",&x,&y);
            printf("%d\n",query(1,x,y));
        }
    return 0;
}

到此這篇關(guān)于C語(yǔ)言詳細(xì)講解樹(shù)狀數(shù)組與線段樹(shù)的文章就介紹到這了,更多相關(guān)C語(yǔ)言樹(shù)狀數(shù)組內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: