樹狀數組

来源:https://www.cnblogs.com/Jason66661010/archive/2020/04/26/12782839.html
-Advertisement-
Play Games

參考https://www.cnblogs.com/xenny/p/9739600.html 樹狀數組與線段樹的區別 1. 兩者在複雜度上同級, 但是樹狀數組的常數明顯優於線段樹, 其編程複雜度也遠小於線段樹. 2. 樹狀數組的作用被線段樹完全涵蓋, , 但是線段樹能夠解決的問題樹狀數組未必能夠解決 ...


參考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.

image-20200421090900644

用途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的首碼和 =\sum_{i=1}{p}a[i]=\sum_{i=1}{p}\sum_{j=1}^{i}d[j]

在等式最右側的式子\sum_{i=1}{p}\sum_{j=1}{i}d[j]中，d[1]被用了p次，d[2]被用了p-1次……那麼我們可以寫出：

位置p的首碼和 =\sum_{i=1}{p}\sum_{j=1}{i}d[j]=\sum_{i=1}{p}d[i]*(p-i+1)=(p+1)*\sum_{i=1}{p}d[i]-\sum_{i=1}^{p}d[i]*i

那麼我們可以維護兩個數組的首碼和：
一個數組是 sum1[i]=d[i]
另一個數組是 sum2[i]=d[i]*i

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

區間修改 單點查詢

二維首碼和：

sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j]

那麼我們可以令差分數組d[i][j]表示a[i][j]與 a[i-1][j]+a[i][j-1]-a[i-1][j-1]的差。

下麵是給最中間的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;
    }
}

您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 自定義Antd Pro 預設元素
    "概要" "通用元素" "修改的方式" "主頁面" "標簽上的圖標" "logo 和 系統名稱" "footer 的配置" "loading 頁面" "最終效果" 概要 使用 Antd Pro 來開發前端項目時, 生成的項目模板中, 一些基本的元素都是和 Antd Pro 項目相關的. 比如, 系統 ...
  • JS中的基本類型和引用類型
    內置類型 JS 中七種內置類型（null，undefined，boolean，number，string，symbol，object）又分為兩大類型 兩大類型： 基本類型： ，`undefined boolean number string symbol` 引用類型Object： ， ， ， 等 存 ...
  • 前端程式員的進階
    前言 如何成為一名優秀的前端工程師 1. 要有自己的前端知識體系 1. 逐步完善自己的三大能力，首先是編程能力，其次是工程能力，最後是架構能力 1. 在工作中完善自己的領域知識，如教育類，電商類等等 "構建自己的知識體系" 構建自己的知識體系，就是就是把一些零碎的，分散的，相對獨立的知識概念或者觀點 ...
  • JS的賦值與深淺拷貝實例
    賦值 基本類型： 傳值，在棧記憶體中的數據發生數據變化的時候，系統會自動為新的變數分配一個新的之值在棧記憶體中，兩個變數相互獨立，互不影響的 引用類型： 傳址，只改變指針的指向，指向同一個對象，兩個變數相互干擾 淺拷貝 對於基本類型，淺拷貝是對值的複製，拷貝前後對象的基本數據類型互不影響 對於引用類型來 ...
  • 系統模塊劃分設計的思考
    系統模塊劃分設計的思考 前言 首先明確一下，這裡所說的系統模塊劃分，是針對client，service，common這樣的技術劃分，而不是針對具體業務的模塊劃分。避免由於歧義，造成你的時間浪費。 直接原因 公司內部某技術團隊，在引用我們系統的client包時，啟動失敗。 失敗原因是由於client下 ...
  • Flutter沉浸式狀態欄/AppBar導航欄/仿鹹魚底部凸起導航
    Flutter中如何實現沉浸式透明Statusbar狀態欄效果？ 如下圖：狀態欄是指android手機頂部顯示手機狀態信息的位置。android 自4.4開始新加入透明狀態欄功能，狀態欄可以自定義顏色背景，使titleBar能夠和狀態欄融為一體，增加沉浸感。 如上圖Flutter狀態欄預設為黑色半透 ...
  • 如何保證kafka消息不丟失
    背景 這裡的kafka值得是broker,broker消息丟失的邊界需要對齊一下： 1 已經提交的消息 2 有限度的持久化 如果消息沒提交成功，並不是broke丟失了消息； 有限度的持久化（broker可用） 生產者丟失消息 這個發送消息的方式是非同步的；fire and forget,發送而不管結果 ...
  • Java 虛擬機中的運行時數據區分析
    本文基於 JDK1.8 闡述分析 運行過程 我們都知道 Java 源文件通過編譯器編譯後，能產生相應的 .Class 文件，也就是位元組碼文件。而位元組碼文件通過 Java 虛擬機中的解釋器，編譯成特定機器上的機器碼。 跨平臺的特性 Java 能跨平臺的原因是因為：不同的平臺有不同的 JVM 版本，一個 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類