查找范围 L 到 R 中大于 K 的元素数量 (离线查询)

Fenwick 树，也称为二叉索引树 (BIT)，是一种数据结构，主要用于有效地执行数组上的动态累积频率搜索。它对于基于范围的计算非常有用，尤其是在数据集是静态的或更新不频繁时。Fenwick 树可用于计算给定范围 [L, R] 内大于指定值的元素数量。

Fenwick 树到底是什么？

Fenwick 树是一种灵活的数据结构，可用于对数组进行高效的前缀和计算。它专为累积频率操作而设计，在更新和查询时具有对数时间复杂度。其易用性和效率使其成为处理各种编程挑战中的基于范围操作的热门选择。

结构和构建

构建 Fenwick 树涉及在树的不同点存储累积量。构建大小为 N 的数组的 Fenwick 树需要执行以下步骤：

初始化：首先，创建一个大小为 N+1 的零数组。该数组将作为构建 Fenwick 树的基础。

构建：遍历原始数组，通过根据需要添加项目来更新 Fenwick 树。树的修改取决于索引的二进制编码，并使用位运算来有效浏览和更新树节点。

查询操作

Fenwick 树非常适合基于范围的搜索，尤其是前缀和查询。执行前缀和查询的算法非常简单。

查询：要计算原始数组中某个索引“i”之前的累积总和，请遍历 Fenwick 树，并根据“i”的二进制表示考虑适当的区间。将这些区间相加即可获得所需的结果。

算法

1. 排序查询：根据“R”值对查询进行升序排序。
2. Fenwick 树初始化：为提供的数组创建一个 Fenwick 树。
3. 初始化结果数组：创建一个数组，用于保存每个查询的结果。
4. 处理查询：遍历排序后的查询，并使用 Fenwick 树计算范围 [L, R] 内大于“K”的条目数量。根据需要更新结果数组。
5. 结果：显示所有查询的结果。

伪代码

实施

输出

说明

• FenwickTree 是一个表示 Fenwick 树数据结构的类。
• __init__(self, size)：使用给定的大小初始化 Fenwick 树，并创建一个大小为 size + 1、元素初始化为零的二叉索引树 (BIT) 数组 (self.bit)。
• update(self, idx, val)：通过将 val 添加到索引 idx 的元素并将更新基于二叉索引树逻辑传播到树中来更新 Fenwick 树。
• query(self, idx)：通过根据二叉索引树逻辑对元素求和来检索 Fenwick 树中索引 idx 之前的前缀和。
• count_elements_greater_than_k(arr, queries)：此函数接受一个数组 arr 和一系列查询。
• 它使用查询中的最大 R 值或数组的长度（以较大者为准）来确定大小，并初始化 Fenwick 树 fenwick。
• 该函数根据查询的 R 值（范围的上限）对查询进行排序。
• 对于排序后的每个查询 [L, R, K]

它通过从 Fenwick 树中索引 R 和 L - 1 处的累积和中减去来计算范围 [L, R] 中大于“K”的元素的数量。

它通过增加元素 arr[L - 1] 的计数来更新 Fenwick 树。