使用树状数组（离线查询），将范围L到R中大于K的元素数量计算出来

在计算机科学领域，我们必须处理大型数据集，其中包括查询选择和更新操作。以较低的时间复杂度实时执行这些操作对于开发人员来说是一项具有挑战性的任务。

使用 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 = 8
Output: 
2

什么是离线查询？

离线查询是对预先确定的数据集执行的查询操作。换句话说，这些操作仅对那些在处理查询时没有进一步修改的数据集执行。

使用芬威克树

在这里，我们将使用芬威克树，它的每个节点都有向量，其中按顺序包含数组的所有元素。然后，我们使用二分搜索来回答每个查询并计算元素的数量。

• 创建两个函数，updateTree() 和total()，分别用于更新和检索BIT中的前缀和。

• 接下来，创建另一个函数，该函数将计算 L 到 R 范围内大于“K”的元素。该函数接受输入值“arr”、“N”、“L”、“R”和“K”。

• 计数是用最大范围N的累加和减去K的累加和来计算的。

为了排除超出范围的元素，减去L-1的累加和（如果L大于1）。

示例

#include <iostream>
#include <vector>
using namespace std;

// Updating the Fenwick Tree
void updateTree(vector<int>& BIT, int index, int value) {
   while (index < BIT.size()) {
      BIT[index] += value;
      index += index & -index;
   }
}

int total(vector<int>& BIT, int index) {
   int result = 0;
   while (index > 0) {
      result += BIT[index];
      index -= index & -index;
   }
   return result;
}

// Counting the number of elements
int elementsGreaterThanK(vector<int>& arr, int N, int K, int L, int R) {
   vector<int> BIT(N+1, 0);

   for (int i = L; i <= R; i++) {
      updateTree(BIT, arr[i], 1);
   }

   int count = total(BIT, N) - total(BIT, K);
   if (L > 1) {
      count -= total(BIT, L-1);
   }
   return count;
}

int main() {
   vector<int> 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 <iostream>
#include <vector>
using namespace std;
struct Query {
   int index;
   int val;
};

void updateTree(vector<int>& BIT, int index, int value) {
   while (index < BIT.size()) {
      BIT[index] += value;
      index += index & -index;
   }
}

int total(vector<int>& BIT, int index) {
   int result = 0;
   while (index > 0) {
      result += BIT[index];
      index -= index & -index;
   }
   return result;
}

vector<int> elementsGreaterThanK(vector<int>& arr, vector<Query>& queries, int K) {
   int N = arr.size();
   vector<int> BIT(N+1, 0);
   vector<int> result;

   for (int i = 0; i < N; i++) {
      updateTree(BIT, i+1, (arr[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<int> arr = {3, 14, 32, 7, 11, 5, 8, 6, 16, 2, 15};
   vector<Query> queries = {{2, 4}, {5, 3}, {3, 6}, {0, 3}};
   int K = 2;

   vector<int> 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: 2
Number of elements greater than 2: 5
Number of elements greater than 2: 3
Number of elements greater than 2: 0

结论

我们可以简单地从索引 L 到 R 迭代数组，并在每次数组元素大于 K 时加 1，以便找到每个查询的答案。然而，为了降低时间复杂度，我们使用Fenwick树来进行此类查询操作。我们还可以使用线段树和稀疏表来代替Fenwick树来进行此类查询操作。

以上是使用树状数组（离线查询），将范围L到R中大于K的元素数量计算出来的详细内容。更多信息请关注PHP中文网其他相关文章！