查询数组中大于或等于给定数字的元素数量并进行更新- 技术经验 -卓越飞翔博客

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

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

第 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

结论

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

语法

算法

遵循的方法

方法 1

示例 1

输出

方法-2

示例 2

输出

结论

相关推荐