C語言詳細(xì)講解樹狀數(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ù)列。
接下來 m 行，每行包含三個(gè)整數(shù) k,a,b （k=0，表示求子數(shù)列[a,b]的和；k=1，表示第 a 個(gè)數(shù)加 b）。
數(shù)列從 1 開始計(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
這道題我最開始的想法就是只用前綴和，但后來發(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è)賮矸治鲆幌聵錉顢?shù)組是怎樣的。
1、lowbit(x):返回x的最后一位1
2、add(x,v):在x位置加上v，并將后面相關(guān)聯(lián)的位置也加上v
3、query(x):詢問x的前綴和
時(shí)間復(fù)雜度 O(logn)
假設(shè)原序列為a，樹狀數(shù)組序列為c,那么是怎么由原序列得到樹狀數(shù)組序列的呢？(可以把c理解為a的前綴和序列，只是前綴和關(guān)系不像一般前綴和那樣簡(jiǎn)單、線性)
1. 首先，將一維的樹狀數(shù)組序列c看成多層的序列，c[i]屬于第幾層，取決于i的二進(jìn)制表示中最后一個(gè)1后面有幾個(gè)0，有幾個(gè)0就在第幾層，顯而易見,當(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. 如何通過樹狀數(shù)組求前綴和？
由上面公式知道，想要求序列aa中11到xx的和，則應(yīng)該是：
因而可得代碼：
int res=0; for(int i=x;i>0;i-=lowbit(x)) res+=c[i]; return res;
如何通過樹狀數(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í)候用一般前綴和算法呢？
這就要明白這兩個(gè)算法的本質(zhì)區(qū)別：
一般前綴和算法是離線算法，它不支持動(dòng)態(tài)的改變單個(gè)元素的值，或者說改變單個(gè)元素值后，重新維護(hù)前綴和所花費(fèi)的代價(jià)很大。
樹狀數(shù)組是在線算法，支持動(dòng)態(tài)改變單個(gè)元素的值，以很小的代價(jià)動(dòng)態(tài)維護(hù)前綴和。
所以當(dāng)僅僅需要用到前綴和，不涉及動(dòng)態(tài)的改變單個(gè)元素的值時(shí)，首選一般前綴和算法，否則就用樹狀數(shù)組。
數(shù)星星
天空中有一些星星，這些星星都在不同的位置，每個(gè)星星有個(gè)坐標(biāo)。
如果一個(gè)星星的左下方（包含正左和正下）有 k 顆星星，就說這顆星星是 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ù)目。
換句話說，給定 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ù)目；
接下來 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
這題看起來是二維的，但是實(shí)際上我們可以不用考慮y，因?yàn)樾切前?y 坐標(biāo)增序給出，y 坐標(biāo)相同的按 x 坐標(biāo)增序給出，所以我們只需要實(shí)時(shí)更新一下我們的樹狀數(shù)組就可以了。
如何更新？
這個(gè)題目本身就是一道利用前綴和思想做的題目。就和開頭所說過的一樣，只要求出有多少個(gè)星星的 x 值不小于該星星的 x 值就可以了，而這個(gè)過程就是利用的前綴和。
那讓我們先用前綴和的思想來看一下這道題目。
假設(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í)我們是利用了這一特性來簡(jiǎn)化我們的算法的。其實(shí)如果這道題目輸入的 y 并不按照不降原則來輸入的話，那么這種算法就不對(duì)了。
現(xiàn)在說明一下為什么要實(shí)時(shí)計(jì)算，因?yàn)楹竺孑斎氲?x 值很可能比我們前面輸入的 x 值要小，因?yàn)閿?shù)據(jù)輸入的是按y不降輸入的，而 x 可以是任意的，如果我們不實(shí)時(shí)計(jì)算，而是等到全部處理完再計(jì)算的話，會(huì)導(dǎo)致 “x 雖然比你大但是 y 比你小的情況”，而這種情況是顯然不符合我們的題意的，所以說我們這種利用前綴和的算法是很特殊的，是僅僅針對(duì)于這個(gè)題目的。
能用到數(shù)據(jù)結(jié)構(gòu)的算法的題目，往往是根據(jù)數(shù)據(jù)結(jié)構(gòu)的特性來決定的。比如這個(gè)題目我們?yōu)槭裁匆脴錉顢?shù)組來處理？是因?yàn)槲覀冞@里要運(yùn)用前綴和，以及更新前綴和，而這恰好符合樹狀數(shù)組的特性，所以我們利用了它。
所以本題的思考思路總結(jié)應(yīng)該是：
1、分析題目，通過輸入特性判斷解題方法
2、想想暴力解法怎么做？利用前綴和，每次用O(n)的時(shí)間復(fù)雜度更新前綴和
3、想想是否能優(yōu)化？
4、想到樹狀數(shù)組優(yōu)化
5、利用樹狀數(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;
}線段樹
動(dòng)態(tài)求連續(xù)區(qū)間和
我們還是以動(dòng)態(tài)求連續(xù)區(qū)間和為例
線段樹基于分治思想
那么我們可以把每一個(gè)區(qū)間一分為二，這樣就把整個(gè)區(qū)間變成了一棵樹。
這樣的話我們可以看一下兩個(gè)操作，因?yàn)槭菢渖希沂且豢脻M二叉樹，所以深度一定是O(logN)的。
1、pushup(u):用子節(jié)點(diǎn)信息來更新當(dāng)前節(jié)點(diǎn)信息（把信息往上傳遞）
2、build(u,l,r):在一段區(qū)間上初始化線段樹，其中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
我們來看一些基本的操作吧！
首先是上傳的操作，線段樹的意思就是用左右子樹更新根節(jié)點(diǎn)。
怎么寫呢？
這個(gè)的話我們結(jié)合著拿到題寫吧。
就是單點(diǎn)修改，區(qū)間查詢。
線段樹的話一般使用結(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;
}
然后就是建樹操作，在最開始需要把樹“建造出來”。
這個(gè)可以直接遞歸建立樹。
這個(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;
}
線段樹的思想上面已經(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ū)間最大值
輸入一串?dāng)?shù)字，給你 M 個(gè)詢問，每次詢問就給你兩個(gè)數(shù)字 X,Y，要求你說出 X 到 Y 這段區(qū)間內(nèi)的最大數(shù)。
輸入格式
第一行兩個(gè)整數(shù) N,M 表示數(shù)字的個(gè)數(shù)和要詢問的次數(shù)；
接下來一行為 N 個(gè)數(shù)；
接下來 M 行，每行都有兩個(gè)整數(shù) X,Y。
輸出格式
輸出共 M 行，每行輸出一個(gè)數(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
這題和動(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];//二叉樹 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è)子樹當(dāng)中取最大
}
void build(int u,int l,int r)//初始化線段樹 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;//初始化二叉樹 只與結(jié)構(gòu)有關(guān) 與本身數(shù)據(jù)無關(guān) 所以mid = l+r>>1
build(u<<1,l,mid),build(u<<1|1,mid+1,r);//遞歸找兩個(gè)子樹
pushup(u);//當(dāng)前的最大值等于兩個(gè)子樹間的最大值
}
}
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);//如果左邊有包含部分 則更新左子樹
if(r>=mid+1)maxv=max(maxv,query(u<<1|1,l,r));//如果右邊有包含部分 則更新右子樹
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);//初始化線段樹
int x,y;
while(m--)
{
scanf("%d%d",&x,&y);
printf("%d\n",query(1,x,y));
}
return 0;
}到此這篇關(guān)于C語言詳細(xì)講解樹狀數(shù)組與線段樹的文章就介紹到這了,更多相關(guān)C語言 樹狀數(shù)組內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
使用Objective-C獲取IPHONE手機(jī)IMSI序列號(hào)
這篇文章主要介紹了使用Objective-C獲取IPHONE手機(jī)IMSI序列號(hào)的方法以及通過IMSI序列號(hào)獲取運(yùn)營(yíng)商、手機(jī)號(hào)的方法，非常的實(shí)用，有需要的小伙伴可以參考下。2015-04-04
C++ Qt開發(fā)之使用QHostInfo查詢主機(jī)地址
Qt 是一個(gè)跨平臺(tái)C++圖形界面開發(fā)庫,利用Qt可以快速開發(fā)跨平臺(tái)窗體應(yīng)用程序,本文將重點(diǎn)介紹如何運(yùn)用QHostInfo組件實(shí)現(xiàn)對(duì)主機(jī)地址查詢功能,希望對(duì)大家有所幫助2024-03-03
這篇文章主要介紹了C++ decltype 說明符，檢查實(shí)體的聲明類型，或表達(dá)式的類型和值類別。下面我們來看看文章中的具體內(nèi)容吧2021-12-12
這篇文章主要介紹了++實(shí)現(xiàn)模板方法模式,本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-07-07
用Visual Studio2017寫C++靜態(tài)庫圖文詳解
這篇文章主要介紹了用Visual Studio2017寫C++靜態(tài)庫的圖文教程,需要的朋友可以參考下2017-04-04
這篇文章主要介紹了C語言中編寫可變參數(shù)函數(shù)的相關(guān)資料,需要的朋友可以參考下2017-07-07
C++課程設(shè)計(jì)之運(yùn)動(dòng)會(huì)管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C++課程設(shè)計(jì)之運(yùn)動(dòng)會(huì)管理系統(tǒng)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-10-10
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)車票管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-05-05
C語言中交換int型變量的值及轉(zhuǎn)換為字符數(shù)組的方法
這篇文章主要介紹了C語言中交換int型變量的值及轉(zhuǎn)換為字符數(shù)組的方法,講解了以不同進(jìn)制將整型數(shù)字轉(zhuǎn)換成字符數(shù)組,需要的朋友可以參考下2016-04-04
Qt+Quick實(shí)現(xiàn)播放音樂和視頻的開發(fā)
這篇文章主要為大家詳細(xì)介紹了如何利用Qt+Quick實(shí)現(xiàn)播放音樂和視頻的開發(fā)，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2023-03-03