Query the number of elements in an array that are greater than or equal to a given number and update it

With the help of segment trees, arrays can be successfully updated and range queries performed. By updating, we can use the known data structure segment tree to count. The number of elements in Array greater than or equal to no.

• Query - Find how many items greater than or similar to x exist in the range [l, r].

• If the range [l, r] completely exceeds the segment represented by the current node of the segment tree, 0 is given.

• counting. The number of elements in the range [l, r] that are greater than or similar to x if the interval [l, r] lies entirely within the segment represented by the current node of the segment tree.

• If not, recursively ping the left and right child nodes of the current node and return the total number of counts collected.

• Update - For the element at index i, add the value of v. We apply the following algorithm to this update -

• If the current node display range of the segment tree does not have index i, no operation is performed.

• If the value of index i is greater than or equal to x, update the count of elements greater than or equal to x in the interval represented by the current node of the line segment tree. If the value of index i is greater than or equal to x, increment it, and then Recursively update the left and right child element nodes of the current node.

• We can run queries in the range [0, n-1] at the root node of the segment tree, where n is the total number. The number of entries in the array greater than or equal to x.

grammar

1. Create segment trees and arrays from scratch -

int M; 
int Z[M]; 
int TreE[4*M]; 
BUILD (1, 0, M-1, Z, TreE); 

2. Perform update (change) procedure -

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.Execute the following query operation -

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. Use query operations to count quantities. Elements greater than or equal to the specified value, update operation to update the array and segment tree -

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

algorithm

Using update, here is a possible way to calculate the number. Array members greater than or equal to the specified value -

• Step 1 - Create an array A of size n to hold the starting value.

• Step 2 - To display a minimum range query, initialize a segment tree T of size 4*n.

• Step 3 - Use the function build (T, A, 1, 0, n-1) to create the line segment tree T, where build(T, A, v, tl, tr ) Create a segment tree T in the range [tl, tr] using the values ​​in A and put the result into node v of T.

• Step 4 - Create an array C of size n and initialize it with an item count greater than or equal to the specified number.

• Step 5 - Create a segment tree S with starting size 4*n to represent the range sum of the count query.

• Step 6 - Call the function build (S, C, 1, 0, n-1), where build(S, C, v, tl, tr) creates the line segment tree S For the range [tl, tr], use the value in C and keep the result in node v of S.

• Step 7 - Respond to each "Count elements greater than or equal to x" query -

To find the minimum value in the range [l, r] of array A, call the function query(T, 1, 0, n-1, l, r). Suppose the result is m.

If m is greater than or equal to x, use the function query(S, 1, 0, n-1, l, r) to get the total number. The number of entries in the interval [l, r] of array C that are greater than or equal to x. Let the result be c.

If not, set c to 0.

• Step 8 - Each type change "Set the value of A[i] to v" -

Update the node v of the line segment tree T in the range [tl,tr], call the function update(T,v,tl,tr,i,val), where update(T,v,tl,tr, i,val) changes node v of segment tree T by setting the value at index i to val.

Use the function update(S, 1, 0, n-1, i, (v >= x)) to update the line segment tree node v in the range [tl, tr], where update(S, v, tl, tr, i, val) Update node v by adding val to the count of items greater than or equal to x.

• Step 9 - Repeat steps 7 and 8 again.

Method to follow

method 1

In the example, we define a vector of type int to represent our array and a threshold of type int above or equal to the number of entries we wish to count. Then use the counttheElements function to generate the initial array and the number of elements greater than or equal to the threshold.

The updatetheElement function accepts an array, the index of the element to be updated, and the new value of the element as parameters, and is then used to update the elements in the array. Finally, we use the counttheElements method again to output the modified array and the new count of elements greater than or equal to the threshold.

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

Output

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

Method-2

The function of each query is to count. array (items) greater than or equal to query[i], decrement all those values ​​by M, and run the remainder of the problem on the updated array. The inputs are two arrays, array[] and query[], with sizes N and Q respectively.

First sort the array [] in ascending order.

Find the element whose element is greater than or equal to query[i] at the first position, such as l.

If there is no such element, return 0 as the response. Otherwise, the response will be 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

结论

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

The above is the detailed content of Query the number of elements in an array that are greater than or equal to a given number and update it. For more information, please follow other related articles on the PHP Chinese website!