数据结构
网络
关系型数据库管理系统 (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
