查询数组中大于或等于给定数字的元素数量并进行更新

借助线段树，数组可以成功更新并进行范围查询。通过更新，我们可以使用已知的数据结构线段树来计数。 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，其中 update(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中文网其他相关文章！