資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學帶更新的統計陣列中大於或等於給定數字的元素個數的查詢
藉助線段樹，可以成功地更新陣列並進行範圍查詢。透過更新，我們可以使用稱為線段樹的資料結構來計算陣列中大於或等於某個數字的元素個數。
查詢 - 找出在 [l, r] 範圍內有多少個專案大於或等於 x。
如果範圍 [l, r] 完全超出線段樹當前節點所代表的線段，則返回 0。
如果區間 [l, r] 完全位於線段樹當前節點所代表的線段內，則計算區間 [l, r] 中大於或等於 x 的元素個數。
如果不是，則遞迴地查詢當前節點的左子節點和右子節點，並返回收集到的計數總和。
更新 - 將值 v 新增到索引 i 處的元素。我們對這個更新應用以下演算法：
如果線段樹的當前節點顯示不包含索引 i 的範圍，則什麼也不做。
如果索引 i 處的值大於或等於 x，則透過遞增來更新線段樹當前節點所代表的區間中大於或等於 x 的元素計數，然後遞迴地更新當前節點的左子節點和右子節點。
我們可以使用範圍 [0, n-1] 線上段樹的根節點執行查詢，其中 n 是陣列中大於或等於 x 的元素總數。
語法
1. 從頭開始建立線段樹和陣列 -
int M; int Z[M]; int TreE[4*M]; BUILD (1, 0, M-1, Z, TreE);
2. 執行更新（更改）過程 -
Void change (int NoDe, BeGiN,EnD,IdX,VaL,TreE []) {
if (BeGiN==EnD) {
Z[IdX]=VaL;
TreE[NoDe]=VaL;
} else {
int MiD= (BeGiN + EnD)/2;
if (BeGiN<=IdX && IdX<=MiD)
change (2*NoDe, BeGiN, MiD, IdX, VaL, TreE);
else
change (2*NoDe+1, MiD+1, EnD, IdX, VaL, TreE);
TreE[NoDe] = TreE[2*NoDe] + TreE[2*NoDe+1];
}
}
3. 執行以下查詢操作 -
int QUERY(int NoDe, BeGiN, EnD, L, R, K, TreE []) {
if(sTaRT > EnD || BeGiN > R || EnD < L)
return 0;
if(BeGiN == EnD)
return A[BeGiN] >= K;
int MiD = (BeGiN + EnD) / 2;
return QUERY(2*NoDe, BeGiN, MiD, L, R, K, TreE) + QUERY (2*NoDe+1, MiD+1, EnD, L, R, K, TreE);
}
4. 使用查詢操作來計算大於或等於指定值的元素個數，使用更新操作來更新陣列和線段樹 -
int IdX, VaL; change(1, 0, n-1, IX, VaL, TreE); int L, R, K; int count = QUERY(1, 0, M-1, L, R, K, TreE);
演算法
使用更新，以下是一種可能的計算陣列中大於或等於指定值的元素個數的方法：
步驟 1 - 建立大小為 n 的陣列 A 來儲存初始值。
步驟 2 - 為表示範圍最小值查詢，初始化大小為 4*n 的線段樹 T。
步驟 3 - 使用函式 build(T, A, 1, 0, n-1) 建立線段樹 T，其中 build(T, A, v, tl, tr) 使用 A 中的值為範圍 [tl, tr] 建立線段樹 T，並將結果放入 T 的節點 v 中。
步驟 4 - 建立大小為 n 的陣列 C，並用大於或等於指定數字的項的計數初始化它。
步驟 5 - 建立初始大小為 4*n 的線段樹 S 來表示計數查詢的區間和。
步驟 6 - 呼叫函式 build(S, C, 1, 0, n-1)，其中 build(S, C, v, tl, tr) 使用 C 中的值為範圍 [tl, tr] 建立線段樹 S，並將結果儲存在 S 的節點 v 中。
步驟 7 - 對於每個“計算大於或等於 x 的元素個數”查詢：
步驟 8 - 對於每個“將 A[i] 的值設定為 v”型別的更改：
步驟 9 - 再次重複步驟 7 和 8。
要查詢陣列 A 的範圍 [l, r] 中的最小值，請呼叫函式 query(T, 1, 0, n-1, l, r)。假設結果是 m。
如果 m 大於或等於 x，則使用函式 query(S, 1, 0, n-1, l, r) 來獲取陣列 C 的區間 [l, r] 中大於或等於 x 的元素總數。設結果為 c。
如果不是，則將 c 設定為 0。
更新範圍 [tl, tr] 上線段樹 T 的節點 v，呼叫函式 update(T, v, tl, tr, i, val)，其中 update(T, v, tl, tr, i, val) 透過將索引 i 處的值設定為 val 來更改線段樹 T 的節點 v。
使用函式 update(S, 1, 0, n-1, i, (v >= x)) 更新範圍 [tl, tr] 上線段樹節點 v，其中 update(S, v, tl, tr, i, val) 透過將 val 新增到大於或等於 x 的項的計數來更新節點 v。
方法
方法 1
在這個例子中，我們定義一個 int 型別的向量來表示我們的陣列，以及一個 int 型別的閾值，我們希望計算大於或等於該閾值的元素個數。然後使用 counttheElements 函式來生成初始陣列以及大於或等於閾值的元素個數。
然後使用 updatetheElement 函式來更新陣列中的一個元素，該函式接受陣列、要更新的元素的索引以及該元素的新值作為引數。最後，我們再次使用 counttheElements 方法來輸出修改後的陣列以及大於或等於閾值的新元素個數。
示例 1
#include <iostream>
#include <vector>
using namespace std;
void updatethenumber(vector<int>& ara, int index, int NEWValues) {
ara[index] = NEWValues;
}
int countthenumber(vector<int>& ara, int threshold) {
int cont = 0;
for (int i = 0; i < ara.size(); i++) {
if (ara[i] >= threshold) {
cont++;
}
}return cont;
}
int main () {
vector<int> ara = {3, 6, 2,8, 4, 7} ;
int threshold = 5;
cout << "Initial array: ";
for(int i = 0;i < ara.size();i++) {
cout << ara[i] << " ";
}cout<<endl;
cout<<"Number of elements >= "<<threshold<< ": ";
cout<<countthenumber(ara, threshold)<<endl;
cout<<"Updating element at index 2 to value 9..."<<endl;
updatethenumber(ara,2,9) ;
cout<<"Updated array: " ;
for(int i = 0;i<ara.size();i++) {
cout<<ara[i]<< " ";
} cout<<endl ;
cout<<"Number of elements >= " << threshold << ": " ;
cout<<countthenumber(ara, threshold)<<endl;
return 0;
}
輸出
Initial array: 3 6 2 8 4 7 Number of elements >= 5: 3 Updating element at index 2 to value 9 Updated array: 3 6 9 8 4 7 Number of elements >= 5: 4
方法 2
每個查詢的作用是計算陣列（專案）中大於或等於 Query[i] 的個數，將所有這些值減去 M，然後在更新後的陣列上執行剩餘的查詢。輸入是兩個陣列，array[] 和 Query[]，大小分別為 N 和 Q。
首先將 array[] 按升序排序。
找到第一個大於或等於 query[i] 的元素，假設為 l。
如果沒有這樣的元素，則返回 0 作為響應。否則，響應將為 N - l。
最後一步是從給定範圍中的每個元素中減去 M，並更改區間 l 到 N - 1 中的線段樹。
示例 2
#include <bits/stdc++.h>
using namespace std;
void build(vector<int>& tosum, vector<int>& a, int l, int r, int rlt){
if (l == r) {
tosum[rlt] = a [l - 1];
return;
}
int m = (l + r) >> 1;
build (tosum, a, l, m, rlt << 1);
build (tosum, a, m + 1, r, rlt << 1 | 1);
}
void push(vector<int>& tosum, vector<int>& toadd, int rlt, int ln, int rn){
if (toadd[rlt]) {
toadd [rlt<< 1] += toadd[rlt];
toadd [rlt << 1 | 1] += toadd[rlt];
tosum [rlt<< 1] += toadd[rlt] * ln;
tosum [rlt << 1 | 1] += toadd[rlt] * rn;
toadd[rlt] = 0;
}
}
void update(vector<int>& tosum, vector<int>& toadd, int L, int R, int C, int l,int r, int rlt){
if (L <= l && r <= R) {
tosum[rlt] += C * (r - l + 1);
toadd[rlt] += C;
return;
}
int m = (l + r) >> 1;
push (tosum, toadd, rlt, m - l + 1,
r - m);
if (L <= m)
update (tosum, toadd, L, R, C, l, m,
rlt << 1);
if (R > m)
update (tosum, toadd, L, R, C, m + 1, r,
rlt << 1 | 1);
}
int query(vector<int>& tosum,
vector<int>& toadd,
int L, int R, int l,
int r, int rlt){
if (L <= l && r <= R) {
return tosum[rlt];
}
int m = (l + r) >> 1;
push (tosum, toadd, rlt, m - l + 1,
r - m);
int ans = 0;
if (L <= m)
ans += query (tosum, toadd, L, R, l, m,
rlt << 1);
if (R > m)
ans += query (tosum, toadd, L, R, m + 1, r,
rlt << 1 | 1);
return ans;
}
void sequMaint(int n, int q,vector<int>& a,vector<int>& b,int m){
sort(a.begin(), a.end());
vector<int> tosum, toadd, ans;
tosum.assign(n << 2, 0);
toadd.assign(n << 2, 0);
build (tosum, a, 1, n, 1);
for (int i = 0; i < q; i++) {
int l = 1, r = n, pos = -1;
while (l <= r) {
int m = (l + r) >> 1;
if (query (tosum, toadd, m, m, 1, n, 1)
>= b[i]) {
r = m - 1;
pos = m;
}
else {
l = m + 1;
}
}
if (pos == -1)
ans.push_back(0);
else {
ans.push_back(n - pos + 1);
update (tosum, toadd, pos, n, -m,
1, n, 1);
}
}
for (int i = 0; i < ans.size(); i++) {
cout << ans[i] << " ";
}
}
int main (){
int A = 4;
int B = 3;
int C = 1;
vector<int> array = {1, 2, 3, 4};
vector<int> query = {4, 3, 1};
sequMaint(A, B, array, query, C);
return 0;
}
輸出
1 2 4
結論
總而言之，線段樹可以成功地用於計算陣列中大於或等於固定值且帶更新的元素個數。我們使用延遲傳播來更新線段樹，而不是更新每個節點。節點的更新在延遲傳播期間進行，直到需要為止。總的來說，透過使用帶有延遲傳播的線段樹，我們可以有效地計算陣列中大於或等於某個值的元素個數，並進行更新。
瀏覽量：539
