參考https://www.cnblogs.com/xenny/p/9739600.html
樹狀陣列與線段樹的區別
1.兩者在復雜度上同級, 但是樹狀陣列的常數明顯優于線段樹, 其編程復雜度也遠小于線段樹.
2.樹狀陣列的作用被線段樹完全涵蓋, 凡是可以使用樹狀陣列解決的問題, 使用線段樹一定可以解決, 但是線段樹能夠解決的問題樹狀陣列未必能夠解決.
樹狀陣列的介紹
(注意陣列的下標時從1開始)
黑色陣列代表原來的陣列（下面用A[i]代替）
紅色結構代表我們的樹狀陣列(下面用C[i]代替)
- C[1] = A[1];
- C[2] = A[1] + A[2];
- C[3] = A[3];
- C[4] = A[1] + A[2] + A[3] + A[4];
- C[5] = A[5];
- C[6] = A[5] + A[6];
- C[7] = A[7];
- C[8] = A[1] + A[2] + A[3] + A[4] + A[5] + A[6] + A[7] + A[8];
規律：
C[i] = A[i - 2k+1] + A[i - 2k+2] + ... + A[i];
k為i的二進制中從最低位到高位連續零的長度
樹狀陣列的例題+代碼
http://acm.hdu.edu.cn/showproblem.php?pid=1166
Input
第一行一個整數T，表示有T組資料，
每組資料第一行一個正整數N（N<=50000）,表示敵人有N個工兵營地，接下來有N個正整數,第i個正整數ai代表第i個工兵營地里開始時有ai個人（1<=ai<=50），
接下來每行有一條命令，命令有4種形式：
(1) Add i j,i和j為正整數,表示第i個營地增加j個人（j不超過30）
(2)Sub i j ,i和j為正整數,表示第i個營地減少j個人（j不超過30）;
(3)Query i j ,i和j為正整數,i<=j，表示詢問第i到第j個營地的總人數;
(4)End 表示結束，這條命令在每組資料最后出現;
每組資料最多有40000條命令
Output
對第i組資料,首先輸出“Case i:”和回車,
對于每個Query詢問，輸出一個整數并回車,表示詢問的段中的總人數,這個數保持在int以內，
Sample Input
1
10
1 2 3 4 5 6 7 8 9 10
Query 1 3
Add 3 6
Query 2 7
Sub 10 2
Add 6 3
Query 3 10
End
Sample Output
Case 1:
6
33
59
代碼
#include <bits/stdc++.h>
using namespace std;
int n,m;
int a[50005],c[50005]; //對應原陣列和樹狀陣列
int lowbit(int x){
return x&(-x);
}
void updata(int i,int k){ //在i位置加上k
while(i <= n){
c[i] += k;
i += lowbit(i);
}
}
int getsum(int i){ //求A[1]~A[i]的和
int res = 0;
while(i > 0){
res += c[i];
i -= lowbit(i);
}
return res;
}
int main(){
int t;
cin>>t;
for(int tot = 1; tot <= t; tot++){
cout << "Case " << tot << ":" << endl;
memset(a, 0, sizeof a);
memset(c, 0, sizeof c);
cin>>n;
for(int i = 1; i <= n; i++){
cin>>a[i];
updata(i,a[i]); //輸入初值的時候，也相當于更新了值
}
string s;
int x,y;
while(cin>>s && s[0] != 'E'){
cin>>x>>y;
if(s[0] == 'Q'){ //求和操作
int sum = getsum(y) - getsum(x-1); //x-y區間和也就等于1-y區間和減去1-(x-1)區間和
cout << sum << endl;
}
else if(s[0] == 'A'){
updata(x,y);
}
else if(s[0] == 'S'){
updata(x,-y); //減去操作，即為加上相反數
}
}
}
return 0;
}
代碼決議：
int lowbit(int x){
return x&(-x);
}
其中的x&(-x)：
當一個偶數與它的負值向與時，結果是能被這個偶數整除的最大的2的n次冪
當一個奇數與它的負值向與時結果一定是1.
用途1 單點更新 區間查詢
單點更新
void updata(int i,int k){ //在i位置加上k
while(i <= n)//注意是小于等于n，不是小于n！！！！
{
c[i] += k;
i += lowbit(i);
}
}
//*************************************
for(int i = 1; i <= n; i++){
cin>>a[i];
updata(i,a[i]); //輸入初值的時候，也相當于更新了值
}
例如i==1：c[1]=c[1]+a[1]; i=i+1=2;
c[2]=c[2]+a[2]; i=i+2=4;
c[4]=c[4]+a[4]; i=i+4=8;
c[8]=c[8]+a[8]; i=i+8=16結束 將a[]陣列中所有需要加a[1]的全都加了
區間查詢
int getsum(int i){
int res = 0;
while(i > 0){
res += c[i];
i -= lowbit(i);
}
return res;
}
例如：求a[1]到a[8]的和：也就是c[8]的值:
res=res+c[8]; i=i-8=0;結束
再例如：求a[1]到a[7]的和：
res=res+c[7] i=i-1=6 a[7]
res=res+c[6] i=i-2=4 a[6] a[5]
res=res+c[4] i=i-4=0 a[4] a[3] a[2] a[1]
用途2：區間更新 單點查詢
這里我們引入差分，利用差分建樹，
規定A[0]=0
A[] =0 1 2 3 5 6 9//原陣列
D[] =0 1 1 1 2 1 3//差分陣列（d[i]=a[i]-a[i-1]）
如果我們把[2,5]區間內值加上2，則變成了
A[] =0 1 4 5 7 8 9
D[] =0 1 3 1 2 1 1
當某個區間[x,y]值改變了，區間內的差值是不變的，只有D[x]和D[y+1]的值發生改變
這樣就把，原來要更新一個區間的值變成了只需要更新兩個點，
代碼：
int n,m;
int a[50005] = {0},c[50005]; //對應原陣列和樹狀陣列
int lowbit(int x)
{
return x&(-x);
}
void updata(int i,int k)
{ //在i位置加上k
while(i <= n)
{
c[i] += k;
i += lowbit(i);
}
}
int getsum(int i)
{ //求D[1 - i]的和，即A[i]值
int res = 0;
while(i > 0)
{
res += c[i];
i -= lowbit(i);
}
return res;
}
int main(){
cin>>n;
for(int i = 1; i <= n; i++)
{
cin>>a[i];
updata(i,a[i] - a[i-1]); //輸入初值的時候，也相當于更新了值
}
//[x,y]區間內加上k
updata(x,k); //d[x]需要增加k,所以相應的c[]陣列中需要增加的都要增加
updata(y+1,-k);
//查詢i位置的值，就是查詢a[i]的值，就是求從d[0]到d[i]的和，就是借c[]陣列用getsum函式求和 （單點查詢）
int sum = getsum(i);
return 0;
}
區間更新：
updata(i,a[i] - a[i-1]);
updata(x,k);
updata(y+1,-k);
單點查詢：
int sum = getsum(i);
用途3：區間查詢 區間更新
思路：https://blog.csdn.net/bestsort/article/details/80796531
怎么求呢？我們基于問題2的“差分”思路，考慮一下如何在問題2構建的樹狀陣列中求前綴和：
位置p的前綴和 =
在等式最右側的式子中，
被用了p次，
被用了
次……那么我們可以寫出：
位置p的前綴和 =
那么我們可以維護兩個陣列的前綴和：
一個陣列是
另一個陣列是
int n,m;
int a[50005] = {0};
int sum1[50005]; //(D[1] + D[2] + ... + D[n])
int sum2[50005]; //(1*D[1] + 2*D[2] + ... + n*D[n])
int lowbit(int x){
return x&(-x);
}
void updata(int i,int k){
int x = i; //因為x不變，所以得先保存i值
while(i <= n){
sum1[i] += k;
sum2[i] += k * (x-1);
i += lowbit(i);
}
}
int getsum(int i){ //求前綴和
int res = 0, x = i;
while(i > 0){
res += x * sum1[i] - sum2[i];
i -= lowbit(i);
}
return res;
}
int main(){
cin>>n;
for(int i = 1; i <= n; i++){
cin>>a[i];
updata(i,a[i] - a[i-1]); //輸入初值的時候，也相當于更新了值
}
//[x,y]區間內加上k
updata(x,k); //A[x] - A[x-1]增加k
updata(y+1,-k); //A[y+1] - A[y]減少k
//求[x,y]區間和
int sum = getsum(y) - getsum(x-1);
return 0;
}
區間更新
void updata(int i,int k){
int x = i; //因為x不變，所以得先保存i值
while(i <= n){
sum1[i] += k;
sum2[i] += k * (x-1);
i += lowbit(i);
}
}
updata(x,k); //A[x] - A[x-1]增加k
updata(y+1,-k); //A[y+1] - A[y]減少k
區間查詢
//求[x,y]區間和
int sum = getsum(y) - getsum(x-1);
用途4：求逆序對
1.逆序對的定義
逆序對就是序列a中ai>aj且i<j的有序對，
方法一：未進行離散化
我們可以先開一個大小為a的最大值的陣列 t，每當讀入一個數時，我們可以用桶排序的思想，將t[a[i]]加上1,然后我們統計t[1]~t[a[i]]的和ans，ans - 1（除掉這個數本身）就是在這個數前面有多少個數比它小，我們只要用i-ans就可以得出前面有多少數比它大，也就是逆序對的數量，
#include <iostream>
#include<string>
#include<algorithm>
#define lowbit(x) (x)&(-x)
using namespace std;
const int maxn = 1e6 + 10;
int c[maxn], n, result;
void update(int i)
{
while (i <= maxn)
{
c[i]++;
i += lowbit(i);
}
}
int getsum(int i)
{
int ans = 0;
while (i > 0)
{
ans += c[i];
i -= lowbit(i);
}
return ans;
}
int main()
{
int temp;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &temp);
update(temp);
result += i - getsum(temp);//使用i減去前面比自己小的就是比自己大的
}
printf("%d\n", result);
return 0;
}
方法二：離散化
現在這個代碼可以在數的最大值比較小的時候可以正確的得出答案，如果資料很大，這回造成我們要開的空間很大，
我們是否可以適當的減少空間的需求呢？我們看看下面這些數：
1 2 3 4 5 10
這6個數我們需要使用大小10的陣列來存盤，我們仔細想想，可以發現中間 6 7 8 9 這4個位置是沒有用到的，也就是說這4個空間被浪費了，怎樣減少這樣的浪費呢？
我們可以在讀完數資料后對他進行從小到大排序，我們用排完序的陣列的下標來進行運算，這樣可以保證小的數依舊小，大的數依舊大，這一步叫做離散化，
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
struct node
{
int data;
int index;
}list[1000];
int aa[1000], c[1000];
int n;
int lowbit(int x)
{
return x&(-x);
}
bool cmp(struct node &a, struct node&b)
{
return a.data < b.data;
}
void update(int i)
{
while (i <=n)
{
c[i] +=1;
i += lowbit(i);
}
}
int getsum(int i)
{
int ans = 0;
while (i > 0)
{
ans += c[i];
i -= lowbit(i);
}
return ans;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &list[i].data);
list[i].index = i;
}
sort(list+1, list + n+1, cmp);
for (int i = 1; i <= n; i++)
aa[list[i].index] = i;
long long answer = 0;
for (int i = 1; i <= n; i++)
{
update(aa[i]);
answer += i - getsum(aa[i]);//用來存盤原數第i個數的order下標是什么
}
cout << answer;
}
或者不用aa陣列
/*for (int i = 1; i <= n; i++)
aa[list[i].index] = i;*/
long long answer = 0;
for (int i = 1; i <= n; i++)
{
update(list[i].index);
answer += i - getsum(list[i].index);//用來存盤原數第i個數的order下標是什么
}
用途5：求區間最大值
void update(int i ,int k)
{
while (i <= n)
{
c[i] = max(c[i], k);
i += lowbit(i);
}
}
int getsum(int i)
{
int ans = 0;
while (i > 0)
{
ans=max(ans, c[i]);
i -= lowbit(i);
}
return ans;
}
改進：
https://blog.csdn.net/u010598215/article/details/48206959?depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-1&utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-1
二維樹狀陣列
C[x][y]記錄的是右下角為(x, y)，高為lowbit(x), 寬為 lowbit(y)的區間的區間和，
單點修改 區間查詢
單點修改
void updata(int x,int y,int k)//將點(x, y)加上z
{ int memy=y;
while(x <= n)
{
y=memy;
while(y<=n)
{
c[x][y]+=k;
y+=lowbit(y);
}
x+=lowbit(x);
}
}
區間查詢
int getsum(int x int y)
{ //求前綴和
int res = 0, memy=y;
while(x>0)
{
y=memy;
while(y>0)
{
res += c[x][y];
y -= lowbit(y);
}
x-=lowbit(x);
}
return res;
}
區間修改 單點查詢
二維前綴和：
那么我們可以令差分陣列表示
與
的差，
下面是給最中間的3*3矩陣加上x時，差分陣列的變化：
0 0 0 0 0
0 +x 0 0 -x
0 0 0 0 0
0 0 0 0 0
0 -x 0 0 +x
效果：
0 0 0 0 0
0 x x x 0
0 x x x 0
0 x x x 0
0 0 0 0 0
void add(int x, int y, int z){
int memo_y = y;
while(x <= n){
y = memo_y;
while(y <= n)
tree[x][y] += z, y += y & -y;
x += x & -x;
}
}
//與單點修改 區間查詢的add一樣
void range_add(int xa, int ya, int xb, int yb, int z){
add(xa, ya, z);
add(xa, yb + 1, -z);
add(xb + 1, ya, -z);
add(xb + 1, yb + 1, z);
}//分別對四個特殊位置進行加減運算
void ask(int x, int y){
int res = 0, memo_y = y;
while(x){
y = memo_y;
while(y)
res += tree[x][y], y -= y & -y;
x -= x & -x;
}
}轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/33448.html
標籤：C++
下一篇：STL之map