在计算机科学领域，我们必须处理大型数据集，其中包括查询选择和更新操作。以较低的时间复杂度实时执行这些操作对于开发人员来说是一项具有挑战性的任务。
使用 Fenwick 树是解决这些基于范围的查询问题的有效方法。
Fenwick Tree 是一种数据结构，可以有效地更新元素并计算表中数字的前缀和。它也称为二叉索引树。
在本文中，我们将讨论如何使用 Fenwick 树查找 L 到 R 范围内大于 K 的元素数量。
输入输出场景
假设您有一个包含 N 个元素的数组，并且您想要查找数组中 L 到 R 范围内大于 K 的元素数量。
Input: arr = {1, 15, 12, 13, 6, 18, 14, 10, 23, 41, 16, 9}N = 11, K = 17, L = 1, R = 8Output: 2
什么是离线查询？
离线查询是对预先确定的数据集执行的查询操作。换句话说，这些操作仅对那些在处理查询时没有进一步修改的数据集执行。
使用芬威克树
在这里，我们将使用芬威克树，它的每个节点都有向量，其中按顺序包含数组的所有元素。然后，我们使用二分搜索来回答每个查询并计算元素的数量。
创建两个函数，updateTree() 和total()，分别用于更新和检索BIT中的前缀和。
接下来，创建另一个函数，该函数将计算 L 到 R 范围内大于“K”的元素。该函数接受输入值“arr”、“N”、“L”、“R”和“K”。
计数是用最大范围N的累加和减去K的累加和来计算的。
为了排除超出范围的元素，减去L-1的累加和（如果L大于1）。
示例
#include #include using namespace std;// Updating the Fenwick Treevoid updateTree(vector& BIT, int index, int value) { while (index < BIT.size()) { BIT[index] += value; index += index & -index; }}int total(vector& BIT, int index) { int result = 0; while (index > 0) { result += BIT[index]; index -= index & -index; } return result;}// Counting the number of elementsint elementsGreaterThanK(vector& arr, int N, int K, int L, int R) { vector BIT(N+1, 0); for (int i = L; i 1) { count -= total(BIT, L-1); } return count;}int main() { vector arr = {0, 5, 2, 3, 6, 8, 7, 1, 8, 4, 6, 9}; int N = 11; // Total range of values int K = 4; // Highest value int L = 1; // Start index of the range int R = 8; // End index of the range int count = elementsGreaterThanK(arr, N, K, L, R); cout << "Number of elements greater than " << K << " in the range [" << L << ", " << R << "]: " << count << endl; return 0;}
输出
Number of elements greater than 4 in the range [1, 8]: 5
替代方法
在这里，我们将创建一个单独的向量来存储查询。每个查询由两个变量组成，index 和 val。 index 用于存储数组中的位置，而val用于存储该索引处元素的值。这种方法使开发人员能够执行各种查询操作。此外，我们使用 BIT 计算每个查询大于 K 的元素数量。
示例
#include #include using namespace std;struct Query { int index; int val;};void updateTree(vector& BIT, int index, int value) { while (index < BIT.size()) { BIT[index] += value; index += index & -index; }}int total(vector& BIT, int index) { int result = 0; while (index > 0) { result += BIT[index]; index -= index & -index; } return result;}vector elementsGreaterThanK(vector& arr, vector& queries, int K) { int N = arr.size(); vector BIT(N+1, 0); vector result; for (int i = 0; i K) ? 1 : 0); } for (auto query : queries) { if (query.val > K) { result.push_back(total(BIT, query.index)); } else { result.push_back(0); } } return result;}int main() { vector arr = {3, 14, 32, 7, 11, 5, 8, 6, 16, 2, 15}; vector queries = {{2, 4}, {5, 3}, {3, 6}, {0, 3}}; int K = 2; vector counts = elementsGreaterThanK(arr, queries, K); for (int count : counts) { cout << "Number of elements greater than " << K << ": " << count << endl; } return 0;}
输出
Number of elements greater than 2: 2Number of elements greater than 2: 5Number of elements greater than 2: 3Number of elements greater than 2: 0
结论
我们可以简单地从索引 L 到 R 迭代数组，并在每次数组元素大于 K 时加 1，以便找到每个查询的答案。然而，为了降低时间复杂度，我们使用Fenwick树来进行此类查询操作。我们还可以使用线段树和稀疏表来代替Fenwick树来进行此类查询操作。
以上就是使用树状数组（离线查询），将范围L到R中大于K的元素数量计算出来的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1444262.html
微信扫一扫 
支付宝扫一扫 
