C語言詳細講解樹狀陣列與線段樹

2022-04-12 19:01:17

樹狀陣列

動態求連續區間和

給定 n 個陣列成的一個數列，規定有兩種操作，一是修改某個元素，二是求子數列 [a,b] 的連續和。

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

第二行包含 n 個整數，表示完整數列。

接下來 m 行，每行包含三個整數 k,a,b （k=0，表示求子數列[a,b]的和；k=1，表示第 a 個數加 b）。

數列從 1 開始計數。

輸出格式
輸出若干行數位，表示 k=0 時，對應的子數列 [a,b] 的連續和。

資料範圍
1≤n≤100000,
1≤m≤100000，
1≤a≤b≤n,
資料保證在任何時候，數列中所有元素之和均在 int 範圍內。

輸入樣例：

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

這道題我最開始的想法就是隻用字首和，但後來發現只用字首和會超時，因為資料範圍

1≤n≤100000,

1≤m≤100000，

1≤a≤b≤n

//字首和會超時
#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("%dn", s2[b] - s2[a-1]);
            
        }
    }
}

然後我們再來分析一下樹狀陣列是怎樣的。

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

2、add(x,v):在x位置加上v，並將後面相關聯的位置也加上v

3、query(x):詢問x的字首和

時間複雜度 O(logn)

假設原序列為a，樹狀陣列序列為c,那麼是怎麼由原序列得到樹狀陣列序列的呢？(可以把c理解為a的字首和序列，只是字首和關係不像一般字首和那樣簡單、線性)
1. 首先，將一維的樹狀陣列序列c看成多層的序列，c[i]屬於第幾層，取決於i的二進位制表示中最後一個1後面有幾個0，有幾個0就在第幾層，顯而易見,當i為奇數時，c[i]是在第0層的
因為lowbit(x)=2^k,k表示x的二進位制表示後面有多少個0
（lowbit(n)求得n的二進位制表示中最後一個1以及往後的0）
可以得到關係：
c[x]=a[x−lowbit(x),x]
此關係描述了序列cc中每個元素是哪一段序列a中元素的和
2. 如何通過樹狀陣列求字首和？
由上面公式知道，想要求序列aa中11到xx的和，則應該是：

因而可得程式碼：

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

如何通過樹狀陣列進行單點修改？

這裡我們給出一個結論：一個結點a[i]或c[i]的父結點為c[i+lowbit(i)]

所以當我們改變a[i]的值時，依次遞迴向上更新父結點的值即可。

程式碼：

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("%dn", query(y) - query(x - 1));
        else add(x, y);
    }

    return 0;
}

最後再對比一下一般字首和和樹狀陣列：

可以看出在修改和查詢操作佔比差不多時，樹狀陣列的效率更高

那麼什麼時候用樹狀陣列，什麼時候用一般字首和演演算法呢？

這就要明白這兩個演演算法的本質區別：

一般字首和演演算法是離線演演算法，它不支援動態的改變單個元素的值，或者說改變單個元素值後，重新維護字首和所花費的代價很大。

樹狀陣列是線上演演算法，支援動態改變單個元素的值，以很小的代價動態維護字首和。

所以當僅僅需要用到字首和，不涉及動態的改變單個元素的值時，首選一般字首和演演算法，否則就用樹狀陣列。

數星星

天空中有一些星星，這些星星都在不同的位置，每個星星有個座標。

如果一個星星的左下方（包含正左和正下）有 k 顆星星，就說這顆星星是 k 級的。

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

例圖中有 1 個 0 級，2 個 1 級，1 個 2 級，1 個 3 級的星星。

給定星星的位置，輸出各級星星的數目。

換句話說，給定 N 個點，定義每個點的等級是在該點左下方（含正左、正下）的點的數目，試統計每個等級有多少個點。

輸入格式
第一行一個整數 N，表示星星的數目；

接下來 N 行給出每顆星星的座標，座標用兩個整數 x,y 表示；

不會有星星重疊。星星按 y 座標增序給出，y 座標相同的按 x 座標增序給出。

輸出格式
N 行，每行一個整數，分別是 0 級，1 級，2 級，……，N−1 級的星星的數目。

資料範圍
1≤N≤15000,
0≤x,y≤32000

輸入樣例：

5
1 1
5 1
7 1
3 3
5 5

輸出樣例：

1
2
1
1
0

這題看起來是二維的，但是實際上我們可以不用考慮y，因為星星按 y 座標增序給出，y 座標相同的按 x 座標增序給出，所以我們只需要實時更新一下我們的樹狀陣列就可以了。

如何更新？

這個題目本身就是一道利用字首和思想做的題目。就和開頭所說過的一樣，只要求出有多少個星星的 x 值不小於該星星的 x 值就可以了，而這個過程就是利用的字首和。

那讓我們先用字首和的思想來看一下這道題目。

假設現在存在一個字首和陣列 sum ，那麼每當我們輸入一個 x 的時候，我們都需要把 x 後面（包含x）的所有字首和都加上 1 ，(因為在 x 後面的數都比 x 大，所以需要更新後面所有的字首和)。然後我們在每次輸入 x 的時候都實時更新一下字首和並且實時計算一下我們的星星的等級就可以了。

這裡為什麼要強調實時計算星星等級的值呢？

因為我們這種操作方法是忽略了 y 的，之所以可以忽略 y 是因為題目輸入的原因，所以其實我們是利用了這一特性來簡化我們的演演算法的。其實如果這道題目輸入的 y 並不按照不降原則來輸入的話，那麼這種演演算法就不對了。

現在說明一下為什麼要實時計算，因為後面輸入的 x 值很可能比我們前面輸入的 x 值要小，因為資料輸入的是按y不降輸入的，而 x 可以是任意的，如果我們不實時計算，而是等到全部處理完再計算的話，會導致 “x 雖然比你大但是 y 比你小的情況”，而這種情況是顯然不符合我們的題意的，所以說我們這種利用字首和的演演算法是很特殊的，是僅僅針對於這個題目的。

能用到資料結構的演演算法的題目，往往是根據資料結構的特性來決定的。比如這個題目我們為什麼要用樹狀陣列來處理？是因為我們這裡要運用字首和，以及更新字首和，而這恰好符合樹狀陣列的特性，所以我們利用了它。

所以本題的思考思路總結應該是：

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

2、想想暴力解法怎麼做？利用字首和，每次用O(n)的時間複雜度更新字首和

3、想想是否能優化？

4、想到樹狀陣列優化

5、利用樹狀陣列解決題目

請看程式碼：

#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("%dn", level[i]);

    return 0;
}

線段樹

動態求連續區間和

我們還是以動態求連續區間和為例

線段樹基於分治思想

那麼我們可以把每一個區間一分為二，這樣就把整個區間變成了一棵樹。

這樣的話我們可以看一下兩個操作，因為是樹上，而且是一棵滿二元樹，所以深度一定是O(logN)的。

1、pushup(u):用子節點資訊來更新當前節點資訊（把資訊往上傳遞）

2、build(u,l,r):在一段區間上初始化線段樹，其中u表示根結點，l表示左邊界，r表示右邊界

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

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

我們來看一些基本的操作吧！

首先是上傳的操作，線段樹的意思就是用左右子樹更新根節點。

怎麼寫呢？

這個的話我們結合著拿到題寫吧。

就是單點修改，區間查詢。

線段樹的話一般使用結構體維護。

結構體裡想要啥有啥放進去就行了。

struct Node
{
    int l, r;//左右端點區域

    int sum;//各種查詢變數儲存區域

    //最後還有個懶標記區域，一般在區間修改時使用。
}tr[N * 4];//4倍空間

那麼的話pushup的操作就是用左右兩邊的區間更新總區間。

這個的話很簡單，大區間等於小區間的和。

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 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);
    }
}

然後是查詢操作。

這個也不難。

就可以直接判斷區間。

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;
}

線段樹的思想上面已經說完了，那麼就是程式碼了：

#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;
}

數列區間最大值

輸入一串數位，給你 M 個詢問，每次詢問就給你兩個數位 X,Y，要求你說出 X 到 Y 這段區間內的最大數。

輸入格式
第一行兩個整數 N,M 表示數位的個數和要詢問的次數；

接下來一行為 N 個數；

接下來 M 行，每行都有兩個整數 X,Y。

輸出格式
輸出共 M 行，每行輸出一個數。

資料範圍
1≤N≤105,
1≤M≤106,
1≤X≤Y≤N,
數列中的數位均不超過231−1

輸入樣例：

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

輸出樣例：

5
8

這題和動態求連續區間和差不多，直接套就可以了。

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;
int w[N];//數值

struct Node
{
    int l,r,maxv;// 把記錄區間和的sum換成了記錄區間最大值的maxv
}tr[4*N];//二元樹 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);//更新資料 兩個子樹當中取最大
}

void build(int u,int l,int r)//初始化線段樹 u序號 lr具體範圍
{
    if(l==r)tr[u]={l,r,w[r]};//如果只有一個資料 即最大是當前資料
    else 
        {
            tr[u]={l,r};
            int mid=l+r>>1;//初始化二元樹 只與結構有關 與本身資料無關 所以mid = l+r>>1
            build(u<<1,l,mid),build(u<<1|1,mid+1,r);//遞迴找兩個子樹
            pushup(u);//當前的最大值等於兩個子樹間的最大值
        }
}

int query(int u,int l,int r)//u序號 lr要查詢的範圍
{
    if(l<=tr[u].l&&tr[u].r<=r)return tr[u].maxv;//如果要查詢的範圍包含當前範圍則直接返回最值
    else 
        {
            int maxv=0;
            int mid=tr[u].l+tr[u].r>>1;//與本身資料有關 做中間值 用於找包含部分
            if(l<=mid)maxv=query(u<<1,l,r);//如果左邊有包含部分 則更新左子樹
            if(r>=mid+1)maxv=max(maxv,query(u<<1|1,l,r));//如果右邊有包含部分 則更新右子樹
            return maxv;//當前maxv實際是由底層逐層比對返回的在指定區域內的最大值
        }
}

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);//初始化線段樹

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

到此這篇關於C語言詳細講解樹狀陣列與線段樹的文章就介紹到這了,更多相關C語言樹狀陣列內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！

C語言詳細講解樹狀陣列與線段樹

目錄

樹狀陣列

動態求連續區間和

數星星

線段樹

動態求連續區間和

數列區間最大值

熱門文章