C語言樹狀數組與線段樹實例分析

這篇文章主要介紹“C語言樹狀數組與線段樹實例分析”，在日常操作中，相信很多人在C語言樹狀數組與線段樹實例分析問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”C語言樹狀數組與線段樹實例分析”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

樹狀數組

動態求連續區間和

給定 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("%d\n", 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("%d\n", 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("%d\n", 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("%d\n",query(1,x,y));
        }
    return 0;
}

到此，關于“C語言樹狀數組與線段樹實例分析”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！