數據結構與算法-數據結構-樹狀數組

概念

樹狀數組，也叫二叉索引樹（Binary Indexed Tree，BIT），它是用數組來模擬樹形結構。樹狀數組的每個節點存儲的是數組中某一段的和（或其他可合并的信息），通過巧妙的索引方式和樹形結構，能夠在對數時間內完成前綴和的查詢以及單個元素的修改操作。

原理

結構特點：樹狀數組的結構基于二進制位的原理。對于一個數組?C，假設其下標從?1?開始，對于任意下標?i，C[i]?負責維護的區間長度是?i?的二進制表示中最低位的?1?所對應的值。例如，i = 6，二進制表示為?110，最低位的?1?對應的值是?2，所以?C[6]?維護的區間長度為?2，即?C[6]?存儲的是?a[5] + a[6]?的和（假設?a?是原始數組）。

前綴和計算：計算前綴和時，利用樹狀數組的結構特點，通過不斷地訪問父節點來累加區間和。例如，要求?a[1]?到?a[7]?的前綴和，7?的二進制是?111，則依次訪問?C[7]、C[6]、C[4]?并累加它們的值，就能得到前綴和。這是因為?C[7]?包含了?a[7]，C[6]?包含了?a[5] + a[6]，C[4]?包含了?a[1] + a[2] + a[3] + a[4]，恰好覆蓋了?a[1]?到?a[7]?的范圍。

單點更新：當對原始數組中的一個元素進行修改時，需要更新樹狀數組中與之相關的節點。例如，修改?a[i]?的值，那么需要更新所有包含?a[i]?的區間對應的樹狀數組節點。通過不斷地將?i?加上其最低位的?1?來找到需要更新的節點。例如，i = 3，二進制是?11，更新完?C[3]?后，下一個要更新的是?C[4]，因為?3?加上最低位的?1（即?1）得到?4，以此類推，直到超出數組范圍。

處理的問題類型

前綴和查詢：快速計算數組中某一段的前綴和，時間復雜度為?O(logn)，相比樸素的遍歷求和方法（時間復雜度為?O(n)）效率更高。

單點更新：在修改數組中單個元素的值后，能夠快速更新相關的前綴和信息，同樣具有?O(logn)?的時間復雜度。

區間修改和查詢：通過一些技巧，可以將樹狀數組擴展到支持區間修改和區間查詢操作。例如，使用差分思想，將區間修改轉化為單點修改，然后再通過樹狀數組來維護差分后的數組，從而實現高效的區間操作。

注意：如果數據滿足差分的條件，也可以實現區間更新以及區間查詢

一些步驟，功能

1，lowbit

lowbit?函數用于獲取一個整數二進制表示中最低位的?1?所對應的值。例如，對于數字?6，它的二進制表示是?110，最低位的?1?對應的值是?2；對于數字?7，二進制表示是?111，最低位的?1?對應的值是?1。在樹狀數組里，lowbit?至關重要，它能幫助我們快速找到節點之間的父子關系。

代碼：

int lowbit(int x) {

????return x & -x;}

2，get_sum

get_sum?函數用于計算樹狀數組中前?i?個元素的前綴和。它利用樹狀數組的結構特點，通過不斷訪問父節點并累加區間和來實現前綴和的快速計算。

int get_sum(int i) {

????????int sum = 0;

????????while (i > 0) {

????????????sum += tree[i];

????????????i -= lowbit(i);

????????}

????????return sum;

????}

3,update

update?函數用于更新樹狀數組中第?i?個元素的值。當修改原始數組中的某個元素時，需要更新樹狀數組中所有包含該元素的區間節點，以保證前綴和信息的正確性。

void update(int i, int val) {

?????while (i <= n) {

?????????tree[i] += val;

?????????i += lowbit(i);

????}

}

4,初始化O(n)的初始化

-使用前綴和的初始化，先計算a的前綴和數組pre，然后根據c[i]=pre[i]-pre[i-lowbit(i)]來計算

for (int i = 1; i <= n; ++i) {

????????????prefixSum[i] = prefixSum[i - 1] + arr[i - 1];

????????}

????????// 初始化樹狀數組

????????for (int i = 1; i <= n; ++i) {

????????????tree[i] = prefixSum[i] - prefixSum[i - lowbit(i)];

????????}

-使用update做到原地的O(n)的修改

void init() {

?for (int i = 1; i <= n; ++i) {

t[i] += a[i];

int j = i + lowbit(i);

?if (j <= n) t[j] += t[i];

}

?}

練習題：

樓蘭圖騰

在完成了分配任務之后，西部 314 來到了樓蘭古城的西部。相傳很久以前這片土地上（比樓蘭古城還早）生活著兩個部落，一個部落崇拜尖刀（V），一個部落崇拜鐵鍬（∧），他們分別用?V?和?∧?的形狀來代表各自部落的圖騰。

西部 314 在樓蘭古城的下面發現了一幅巨大的壁畫，壁畫上被標記出了?N?個點，經測量發現這?N?個點的水平位置和豎直位置是兩兩不同的。西部 314 認為這幅壁畫所包含的信息與這?N?個點的相對位置有關，因此不妨設坐標分別為?(1,y1?),(2,y2?),?,(n,yn?)，其中?y1?～yn??是?1?到?n?的一個排列。

如圖，圖中的?y1?=1，y2?=5，y3?=3，y4?=2，y5?=4。

西部 314 打算研究這幅壁畫中包含著多少個圖騰，其中?V?圖騰的定義如下（注意：圖騰的形式只和這三個縱坐標的相對大小排列順序有關）1≤i<j<k≤n?且?yi?>yj?,?yj?<yk?；

而崇拜?∧?的部落的圖騰被定義為?1≤i<j<k≤n?且?yi?<yj?，yj?>yk?；

西部 314 想知道，這?n?個點中兩個部落圖騰的數目。因此，你需要編寫一個程序來求出?V?的個數和?∧?的個數。

輸入格式

第一行一個正整數?n；

第二行是?n?個正整數，分別代表?y1?,y2?,?,yn?。

輸出格式

輸出兩個數，中間用空格隔開，依次為?V?的個數和?∧?的個數

分析，很裸的樹狀數組，統計前后的比當前值大的，小的值的數，根據乘法原理，得答案

代碼：


#include <iostream>

#include <cstring>

using std::cin;

using std::cout;

using std::endl;

const int N = 200010;

int n;

int c[N], a[N];

// 計算 x 的最低位 1 代表的值

int lb(int x) {

????return x & -x;

}

// 查詢前綴和

long long get(int x) {

????long long res = 0;

????for (int i = x; i; i -= lb(i)) res += c[i];

????return res;

}

// 更新樹狀數組

void up(int x, int val) {

????for (int i = x; i <=n; i += lb(i)) {

????????c[i] += val;

????}

}

long long preg[N], prel[N];

int main() {

????cin >> n;

????for (int i = 1; i <= n; i++) cin >> a[i];

????for (int i = 1; i <= n; i++) {

????????preg[i] = get(n) - get(a[i]);

????????prel[i] = get(a[i] - 1);

????????up(a[i], 1);

????}

????long long res1 = 0, res2 = 0;

????memset(c, 0, sizeof c);

????for (int i = n; i; i--) {

????????res1 += preg[i] * (get(n) - get(a[i]));

????????res2 += prel[i] * get(a[i] - 1);

????????up(a[i], 1);

????}

????cout << res1 << ' ' << res2 << endl;

????return 0;

}


一個簡單的整數問題

給定長度為?NN?的數列?AA，然后輸入?MM?行操作指令。

第一類指令形如?C l r d，表示把數列中第?l～rl～r?個數都加?dd。

第二類指令形如?Q x，表示詢問數列中第?xx?個數的值。

對于每個詢問，輸出一個整數表示答案。

輸入格式

第一行包含兩個整數?NN?和?MM。

第二行包含?NN?個整數?A[i]A[i]。

接下來?MM?行表示?MM?條指令，每條指令的格式如題目描述所示。

輸出格式

對于每個詢問，輸出一個整數表示答案。

每個答案占一行。

分析：
內核是一個單點查詢和區間修改的題，我們可以通過差分和樹狀數組的合作來解決

代碼：

#include <iostream>

#include <cstring>

using std::cin;

using std::cout;

using std::endl;

const int N = 200010;

int n,m;

int c[N], a[N];

// 計算 x 的最低位 1 代表的值

int lb(int x) {

????return x & -x;

}

// 查詢前綴和

long long get(int x) {

????long long res = 0;

????for (int i = x; i; i -= lb(i)) res += c[i];

????return res;

}

// 更新樹狀數組

void up(int x, int val) {

????for (int i = x; i <=n; i += lb(i)) {

????????c[i] += val;

????}

}

int main() {

????cin >> n>>m;

????for (int i = 1; i <= n; i++) cin >> a[i];

????for (int i = 1; i <= n; i++) {

????????up(i, a[i]-a[i-1]);

????}

????for(int i=0;i<m;i++){

????????char w;

????????cin>>w;

????????if(w=='Q'){

????????????int tmp;

????????????scanf("%d",&tmp);

????????????cout<<get(tmp)<<endl;

????????}else {

????????????int l,r,d;

????????????scanf("%d%d%d",&l,&r,&d);

????????????up(l,d);

????????????up(r+1,-d);

????????}

????????

????}

????return 0;

}

一個簡單的整數問題2：


給定一個長度為?NN?的數列?AA，以及?MM?條指令，每條指令可能是以下兩種之一：

C l r d，表示把?A[l],A[l+1],…,A[r]A[l],A[l+1],…,A[r]?都加上?dd。

Q l r，表示詢問數列中第?l～rl～r?個數的和。

對于每個詢問，輸出一個整數表示答案。

輸入格式

第一行兩個整數?N,MN,M。

第二行?NN?個整數?A[i]A[i]。

接下來?MM?行表示?MM?條指令，每條指令的格式如題目描述所示。

輸出格式

對于每個詢問，輸出一個整數表示答案。

每個答案占一行。

分析：


內核是區間查詢和區間修改，上面的區間修改利用了差分來解決，接下來的區間查詢可以根據貢獻度來幫忙處理

先明確下get_sum的作用，我們想要他求出1~i的數字的和，那么對于區間l~r，就可以通過調用get(r)-get(l-1)來得到答案

接下來的問題就是如何實現get_sum，我們先看看我的之前的get（x）的作用，是求出第x個數字的大小。我們通過下面的操作

發現了黑色的d對于我們黑色部分的貢獻度是i*d[i]，我們的目標是

aim =（n+1）*get(n)-∑i*d[i]，

我們不妨用一個樹狀數組來存儲一下這個i*d[i]，那么我們的aim

aim=（n+1）*get(n,原來的樹狀數組) -get(n,i*d[i]的樹狀數組)

代碼：

#include <cstdio>

#include <cstring>

using namespace std;

const int N = 200010;

long long n, m;

long long c[N], a[N], ci[N];

// 計算 x 的最低位 1 代表的值

long long lb(long long x) {

????return x & -x;

}

// 查詢前綴和

long long get(long long x, long long w[]) {

????long long res = 0;

????for (int i = x; i; i -= lb(i)) res += w[i];

????return res;

}

// 更新樹狀數組

void up(long long x, long long val, long long w[]) {

????for (int i = x; i < N; i += lb(i)) {

????????w[i] += val;

????}

}

int main() {

????scanf("%d %d", &n, &m);

????for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);

????for (int i = 1; i <= n; i++) {

????????up(i, a[i] - a[i - 1], c);

????????up(i, i * (a[i] - a[i - 1]), ci);

????}

????for (int i = 0; i < m; i++) {

????????char w;

????????scanf(" %c", &w); ?// 注意這里的空格，用于消耗掉之前輸入的換行符

????????if (w == 'Q') {

????????????int l,r;

????????????scanf("%d%d", &l,&r);

????????????long long rr=get(r, c) * (r + 1) - get(r, ci);

????????????long long ll=get(l-1, c) * (l ) - get(l-1, ci);

????????????printf("%lld\n", rr-ll);

????????} else {

????????????int l, r, d;

????????????scanf("%d %d %d", &l, &r, &d);

????????????up(l, d, c);

????????????up(r + 1, -d, c);

????????????up(l, l * d, ci);

????????????up(r + 1, -(r + 1)*d , ci);

????????}

????}

????return 0;

} ?

謎一樣的牛：

有?nn?頭奶牛，已知它們的身高為?1～n1～n?且各不相同，但不知道每頭奶牛的具體身高。

現在這?nn?頭奶牛站成一列，已知第?ii?頭牛前面有?AiAi?頭牛比它低，求每頭奶牛的身高。

輸入格式

第?11?行：輸入整數?nn。

第?2..n2..n?行：每行輸入一個整數?AiAi，第?ii?行表示第?ii?頭牛前面有?AiAi?頭牛比它低。
（注意：因為第?11?頭牛前面沒有牛，所以并沒有將它列出）

輸出格式

輸出包含?nn?行，每行輸出一個整數表示牛的身高。

第?ii?行輸出第?ii?頭牛的身高。

分析：

二分+樹狀數組，從后面向前遍歷，通過二分找到第k大的數，然后記錄答案即可，如果不會二分也可以用兩個優先隊列，然后從一個里面pop出來k個，放到另外一個，然后取到第k大的后，都放在一個隊列里面，如此往復

代碼：


#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int N = 100010;

int n;

int a[N];

int ans[N];

int tr[N];

int lowbit(int x)

{

????return x & -x;

}

void add(int x, int c)

{

????for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;

}

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 = 2; i <= n; i ++ ) scanf("%d", &a[i]);

????for (int i = 1; i <= n; i ++ ) add(i,1);

????for (int i = n; i; i -- )

????{

????????int k = a[i] + 1;

????????int l = 1, r = n;

????????while (l < r)

????????{

????????????int mid = l + r >> 1;

????????????if (sum(mid) >= k) r = mid;

????????????else l = mid + 1;

????????}

????????ans[i] = r;

????????add(r, -1); ????//刪除

????}

????for (int i = 1; i <= n; i ++ ) printf("%d\n", ans[i]);

????return 0;

}

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/pingmian/73218.shtml
繁體地址，請注明出處：http://hk.pswp.cn/pingmian/73218.shtml
英文地址，請注明出處：http://en.pswp.cn/pingmian/73218.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

AI比人腦更強，因為被植入思維模型【19】三腦理論思維模型

AI比人腦更強，因為被植入思維模型【19】三腦理論思維模型

定義 三腦理論思維模型是由美國神經科學家保羅麥克萊恩&#xff08;Paul MacLean&#xff09;提出的&#xff0c;該理論認為人類的大腦由三個不同但又相互關聯的部分組成&#xff0c;分別是爬蟲腦&#xff08;Reptilian Brain&#xff09;、邊緣腦&#xff08;Limbic Brain&am…
閱讀更多...
使用 patch-package 優雅地修改第三方依賴庫

使用 patch-package 優雅地修改第三方依賴庫

在前端開發中&#xff0c;有時我們需要對第三方依賴庫進行修改以滿足項目需求。然而&#xff0c;直接修改 node_modules 中的文件并不是一個好方法&#xff0c;因為每次重新安裝依賴時這些修改都會丟失。patch-package 是一個優秀的工具&#xff0c;可以幫助我們優雅地管理這些…
閱讀更多...
馬科維茨均值—方差理論推導過程

馬科維茨均值—方差理論推導過程

下面給出一個詳細的、符號嚴謹、公式連貫的馬科維茨均值—方差理論推導過程&#xff0c;假設你輸入了 nnn 列股票的歷史收盤價數據。我們從數據符號的定義開始&#xff0c;逐步構建所有公式&#xff0c;并詳細解釋每個符號的意義。
閱讀更多...
僅靠prompt，Agent難以自救

僅靠prompt，Agent難以自救

Alexander的觀點很明確&#xff1a;未來 AI 智能體的發展方向還得是模型本身&#xff0c;而不是工作流&#xff08;Work Flow&#xff09;。還拿目前很火的 Manus 作為案例&#xff1a;他認為像 Manus 這樣基于「預先編排好的提示詞與工具路徑」構成的工作流智能體&#xff0c;…
閱讀更多...
【css酷炫效果】純CSS實現懸浮彈性按鈕

【css酷炫效果】純CSS實現懸浮彈性按鈕

【css酷炫效果】純CSS實現懸浮彈性按鈕 緣創作背景html結構css樣式完整代碼效果圖 想直接拿走的老板&#xff0c;鏈接放在這里&#xff1a;https://download.csdn.net/download/u011561335/90492020 緣 創作隨緣&#xff0c;不定時更新。 創作背景 剛看到csdn出活動了&…
閱讀更多...
決策樹基礎

決策樹基礎

決策樹 定義 從根節點開始&#xff0c;也就是擁有全部的數據&#xff0c;找一個維度對根節點開始劃分&#xff0c; 劃分后希望數據整體的信息熵是最小的&#xff0c; 針對劃分出來的兩個節點&#xff0c;我們繼續重復剛才的劃分方式尋找信息熵最小的維度和閾值。 遞歸這個…
閱讀更多...
動態查找表

動態查找表

1.問題分析&#xff1a; 動態查找表是一種可以動態地插入、刪除和查找元素的數據結構。它是基于二叉搜索樹實現的&#xff0c;具有快速的查找和插入操作。 以下是一些關于動態查找表的問題分析&#xff1a; 1. 插入操作&#xff1a;在動態查找表中插入一個元素時&#xff0c…
閱讀更多...
得分匹配的朗之萬動力學——Score-Matching Langevin Dynamics (SMLD)

得分匹配的朗之萬動力學——Score-Matching Langevin Dynamics (SMLD)

得分匹配的朗之萬動力學——Score-Matching Langevin Dynamics (SMLD) 文章目錄 得分匹配的朗之萬動力學——Score-Matching Langevin Dynamics (SMLD)摘要Abstract周報內容0. 上期補充1. 本期的基本思想2. 從一個分布中采樣&#xff08;Sampling from a Distribution&#xff…
閱讀更多...
字節DAPO算法：改進DeepSeek的GRPO算法-解鎖大規模LLM強化學習的新篇章（代碼實現）

字節DAPO算法：改進DeepSeek的GRPO算法-解鎖大規模LLM強化學習的新篇章（代碼實現）

DAPO算法&#xff1a;解鎖大規模LLM強化學習的新篇章 近年來&#xff0c;大規模語言模型&#xff08;LLM&#xff09;在推理任務上的表現令人矚目&#xff0c;尤其是在數學競賽&#xff08;如AIME&#xff09;和編程任務中&#xff0c;強化學習&#xff08;RL&#xff09;成為…
閱讀更多...
【Qt】QWidget的styleSheet屬性

【Qt】QWidget的styleSheet屬性

&#x1f3e0;個人主頁&#xff1a;Yui_ &#x1f351;操作環境&#xff1a;Qt Creator &#x1f680;所屬專欄&#xff1a;Qt 文章目錄 前言1. styleSheet屬性2. 利用styleSheet屬性實現簡單的日夜模式切換2.1 知識補充-計算機中的顏色表示 3. 總結 前言 style?好像前端的st…
閱讀更多...
QT Quick（C++）跨平臺應用程序項目實戰教程 2 — 環境搭建和項目創建

QT Quick（C++）跨平臺應用程序項目實戰教程 2 — 環境搭建和項目創建

目錄 引言 1. 安裝Qt開發環境 1.1 下載Qt安裝包 1.2 安裝Qt 1.3 安裝MSVC編譯器 2. 創建Qt Quick項目 2.1 創建新項目 2.2 項目結構 2.3 運行項目 3. 理解項目代碼 3.1 main.cpp文件 3.2 Main.qml文件 引言 在上一篇文章中&#xff0c;我們介紹了本教程的目標和結…
閱讀更多...
macOS Sequoia 15.3 一直彈出“xx正在訪問你的屏幕”

macOS Sequoia 15.3 一直彈出“xx正在訪問你的屏幕”

&#x1f645; 問題描述 macOS 系統升級后&#xff08;15.2或者15.3均出現過此問題&#xff09;&#xff0c;不管是截圖還是開騰訊會議&#xff0c;只要跟捕捉屏幕有關&#xff0c;都一直彈出這個選項&#xff0c;而且所有軟件我都允許訪問屏幕了&#xff0c;這個不是詢問是否…
閱讀更多...
二叉樹的學習

二叉樹的學習

目錄 樹型結構&#xff08;了解&#xff09; 概念 概念&#xff08;重要&#xff09; 樹的表示形式&#xff08;了解&#xff09; 樹的應用 二叉樹&#xff08;重點&#xff09; 概念 兩種特殊的二叉樹 二叉樹的性質 利用性質做題&#xff08;關鍵&#xff09; 二叉…
閱讀更多...
AbMole新生大鼠腦類器官培養Protocol

AbMole新生大鼠腦類器官培養Protocol

近日&#xff0c;希臘亞里士多德大學塞薩洛尼基分校的研究團隊在《神經科學方法》&#xff08;Journal of Neuroscience Methods&#xff09;期刊上發表了一項引人注目的研究&#xff0c;他們開發了一種基于新生大鼠腦組織的新型類器官培養協議&#xff0c;并展望其在阿爾茨海默…
閱讀更多...
物理環境與安全

物理環境與安全

物理安全的重要性 信息系統安全戰略的一個重要組成部分物理安全面臨問題 環境風險不確定性人類活動的不可預知性 典型的物理安全問題 自然災害環境因素設備安全、介質安全、傳輸安全 場地選擇 區域&#xff1a;避開自然災害高發區環境&#xff1a;原理可能的危險因素抗震&…
閱讀更多...
手動離線安裝NextCloud插件

手動離線安裝NextCloud插件

1、下載離線插件安裝包 進入NextCloud官方插件商城&#xff1a;https://apps.nextcloud.com/ 選擇自己需要的插件軟件 選擇NextCloud對應版本的插件安裝包 2、解壓安裝 進入的到NextCloud安裝目錄的apps目錄 cd /var/www/html/apps 將下載的xxx.tar.gz復制到apps目錄中解…
閱讀更多...
算力100問?第93問：算力資源為何更分散了？

算力100問?第93問：算力資源為何更分散了？

目錄 1、政策驅動與地方投資的盲目性 2、美國芯片斷供與國產替代的陣痛 3、政企市場對私有云的偏好 4、技術標準與供需結構的失衡 5、產業生態與市場機制的滯后 6、破局路徑與未來展望 在大模型和人工智能技術快速發展的背景下，算力資源已成為數字經濟時代的核心基礎設施…
閱讀更多...
基于HTML的郵件發送狀態查詢界面設計示例

基于HTML的郵件發送狀態查詢界面設計示例

以下是一個基于HTML的郵件發送狀態查詢界面設計示例&#xff0c;結合篩選功能、狀態展示和重新發送操作&#xff0c;采用Bootstrap框架實現響應式布局&#xff1a; <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"&…
閱讀更多...
分治-快速排序系列一＞快速排序

分治-快速排序系列一＞快速排序

目錄 題目方法&#xff1a;優化方法&#xff1a;代碼&#xff1a; 題目方法&#xff1a; 忘記快速排序看這里&#xff1a;鏈接: link 優化方法&#xff1a; 代碼&#xff1a; public int[] sortArray(int[] nums) {qsort(nums,0,nums.length-1);return nums;}private void qso…
閱讀更多...
《AI大模型趣味實戰 》第7集：多端適配 個人新聞頭條 基于大模型和RSS聚合打造個人新聞電臺(Flask WEB版) 1

《AI大模型趣味實戰 》第7集：多端適配 個人新聞頭條 基于大模型和RSS聚合打造個人新聞電臺(Flask WEB版) 1

AI大模型趣味實戰 第7集&#xff1a;多端適配 個人新聞頭條 基于大模型和RSS聚合打造個人新聞電臺(Flask WEB版) 1 摘要 在信息爆炸的時代&#xff0c;如何高效獲取和篩選感興趣的新聞內容成為一個現實問題。本文將帶領讀者通過Python和Flask框架&#xff0c;結合大模型的強大…
閱讀更多...
最新文章

Copyright @ 2022~2023