亚洲乱码中文字幕综合,中国熟女仑乱hd,亚洲精品乱拍国产一区二区三区,一本大道卡一卡二卡三乱码全集资源,又粗又黄又硬又爽的免费视频

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

 更新時間：2022年04月12日 15:50:28   作者：小羊努力變強  
顧名思義，樹狀數(shù)組就是用數(shù)組來模擬樹形結構唄。那么衍生出一個問題，為什么不直接建樹，因為樹狀數(shù)組能處理的問題就沒必要建樹。線段樹是一種二叉搜索樹，與區(qū)間樹相似，它將一個區(qū)間劃分成一些單元區(qū)間，每個單元區(qū)間對應線段樹中的一個葉結點

樹狀數(shù)組

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

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

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

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

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

數(shù)列從 1 開始計數(shù)。

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

數(shù)據(jù)范圍
1≤n≤100000,
1≤m≤100000，
1≤a≤b≤n,
數(shù)據(jù)保證在任何時候，數(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

這道題我最開始的想法就是只用前綴和，但后來發(fā)現(xiàn)只用前綴和會超時，因為數(shù)據(jù)范圍

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

然后我們再來分析一下樹狀數(shù)組是怎樣的。

在這里插入圖片描述

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

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

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

時間復雜度 O(logn)

假設原序列為a，樹狀數(shù)組序列為c,那么是怎么由原序列得到樹狀數(shù)組序列的呢？(可以把c理解為a的前綴和序列，只是前綴和關系不像一般前綴和那樣簡單、線性)
1. 首先，將一維的樹狀數(shù)組序列c看成多層的序列，c[i]屬于第幾層，取決于i的二進制表示中最后一個1后面有幾個0，有幾個0就在第幾層，顯而易見,當i為奇數(shù)時，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. 如何通過樹狀數(shù)組求前綴和？
由上面公式知道，想要求序列aa中11到xx的和，則應該是：

在這里插入圖片描述

因而可得代碼：

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

如何通過樹狀數(shù)組進行單點修改？

這里我們給出一個結論：一個結點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;
}

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

在這里插入圖片描述

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

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

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

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

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

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

數(shù)星星

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

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

d

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

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

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

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

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

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

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

輸出格式
N 行，每行一個整數(shù)，分別是 0 級，1 級，2 級，……，N−1 級的星星的數(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

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

如何更新？

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

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

假設現(xiàn)在存在一個前綴和數(shù)組 sum ，那么每當我們輸入一個 x 的時候，我們都需要把 x 后面（包含x）的所有前綴和都加上 1 ，(因為在 x 后面的數(shù)都比 x 大，所以需要更新后面所有的前綴和)。然后我們在每次輸入 x 的時候都實時更新一下前綴和并且實時計算一下我們的星星的等級就可以了。

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

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

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

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

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

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

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

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

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

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

請看代碼：

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

線段樹

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

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

線段樹基于分治思想

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

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

在這里插入圖片描述

1、pushup(u):用子節(jié)點信息來更新當前節(jié)點信息（把信息往上傳遞）

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

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

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

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

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

怎么寫呢？

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

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

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

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

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

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

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

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

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

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

然后是查詢操作。

這個也不難。

就可以直接判斷區(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;
}

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

#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ū)間最大值

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

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

接下來一行為 N 個數(shù)；

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

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

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

輸入樣例：

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

輸出樣例：

5
8

這題和動態(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];//二叉樹 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ù) 兩個子樹當中取最大
}

void build(int u,int l,int r)//初始化線段樹 u序號 lr具體范圍
{
    if(l==r)tr[u]={l,r,w[r]};//如果只有一個數(shù)據(jù) 即最大是當前數(shù)據(jù)
    else 
        {
            tr[u]={l,r};
            int mid=l+r>>1;//初始化二叉樹 只與結構有關 與本身數(shù)據(jù)無關 所以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;//與本身數(shù)據(jù)有關 做中間值 用于找包含部分
            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實際是由底層逐層比對返回的在指定區(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);//初始化線段樹

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

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

相關文章

最新評論