查詢數組中大於或等於給定數字的元素數量並進行更新

借助線段樹，陣列可以成功更新並進行範圍查詢。透過更新，我們可以使用已知的資料結構線段樹來計數。 Array 中大於或等於 no 的元素數。

• 查詢 - 找出 [l, r] 範圍內存在多少個大於或類似 x 的項目。

• 如果範圍 [l, r] 完全超出線段樹目前節點所表示的線段，則給予 0。

• 數數。如果區間 [l, r] 完全位於線段樹目前節點所表示的線段內，則範圍 [l, r] 中大於或類似 x 的元素的數量。

• 如果沒有，則遞歸 ping 目前節點的左右子節點，傳回收集到的計數總數。

• 更新 - 對於索引 i 處的元素，新增 v 的值。我們對此更新應用以下演算法 -

• 如果線段樹的目前節點顯示範圍沒有索引 i，則不執行任何動作。

• 如果索引i 的值大於或等於x，則更新線段樹目前節點表示的區間內大於或等於x 的元素計數，如果索引i 的值大於或等於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) 建立線段樹S對於範圍[tl, tr]，使用C 中的值並將結果保留在S 的節點v 中。

• 第 7 步 - 回應每個「計數大於或等於 x 的元素」查詢 -

要找出陣列 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。

• 第 8 步 - 每次型別變更「將 A[i] 的值設為 v」 -

#在範圍[tl,tr]上更新線段樹T的節點v，呼叫函數update(T,v,tl,tr,i,val)，其中up​​date(T,v,tl,tr, i,val)透過將索引i 處的值設為val 來變更線段樹T 的節點v。

使用函數update(S, 1, 0, n-1, i, (v >= x)) 更新範圍[tl, tr] 的線段樹節點v，其中up​​date(S, v, tl, tr, i, val) 透過將val 加到大於或等於x 的項目計數來更新節點v。

• 第 9 步 - 再次重複第 7 步和第 8 步。

遵循的方法

方法 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

每個查詢的作用就是數數。大於或等於查詢 [i] 的陣列（項），將所有這些值遞減 M，然後在更新的陣列上執行剩餘的問題。輸入是兩個數組，數組[]和查詢[]，大小分別為N和Q。

首先對數組[]進行升序排序。

在第一個位置尋找元素大於或等於 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

结论

综上所述，线段树可以成功地用于计数。数组中大于或等于固定值并进行更新的元素的数量。我们使用惰性传播来更新线段树，而不是更新每个节点。对节点的更新是在延迟传播期间完成的，直到需要为止。总的来说，我们可以有效地数出没有。通过使用具有延迟传播的线段树，数组中大于或等于特定值且发生变化的元素。

以上是查詢數組中大於或等於給定數字的元素數量並進行更新的詳細內容。更多資訊請關注PHP中文網其他相關文章！