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

夏浩酱_3762

夏浩酱_3762

2023-09-02

1530人浏览

转载

使用树状数组(离线查询),将范围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

什么是离线查询?

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

使用芬威克树

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

AILOGO
AILOGO

AILOGO是一款由 123LOGO 提供的在线 AI Logo 设计生成工具。

下载
  • 创建两个函数,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, 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  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 <h3>输出</h3>
<pre class="brush:php;toolbar:false;">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, 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  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 <h3>输出</h3>
<pre class="brush:php;toolbar:false;">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树来进行此类查询操作。

相关文章

PHP速学视频免费教程(入门到精通)
PHP速学视频免费教程(入门到精通)

PHP怎么学习?PHP怎么入门?PHP在哪学?PHP怎么学才快?不用担心,这里为大家提供了PHP速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
treenode的用法
treenode的用法

​在计算机编程领域,TreeNode是一种常见的数据结构,通常用于构建树形结构。在不同的编程语言中,TreeNode可能有不同的实现方式和用法,通常用于表示树的节点信息。更多关于treenode相关问题详情请看本专题下面的文章。php中文网欢迎大家前来学习。

2023.12.01

2941

7

C++ 高效算法与数据结构
C++ 高效算法与数据结构

本专题讲解 C++ 中常用算法与数据结构的实现与优化,涵盖排序算法(快速排序、归并排序)、查找算法、图算法、动态规划、贪心算法等,并结合实际案例分析如何选择最优算法来提高程序效率。通过深入理解数据结构(链表、树、堆、哈希表等),帮助开发者提升 在复杂应用中的算法设计与性能优化能力。

2025.12.22

416

20

深入理解算法:高效算法与数据结构专题
深入理解算法:高效算法与数据结构专题

本专题专注于算法与数据结构的核心概念,适合想深入理解并提升编程能力的开发者。专题内容包括常见数据结构的实现与应用,如数组、链表、栈、队列、哈希表、树、图等;以及高效的排序算法、搜索算法、动态规划等经典算法。通过详细的讲解与复杂度分析,帮助开发者不仅能熟练运用这些基础知识,还能在实际编程中优化性能,提高代码的执行效率。本专题适合准备面试的开发者,也适合希望提高算法思维的编程爱好者。

2026.01.06

437

22

C++ 数据结构与算法实现教程合集
C++ 数据结构与算法实现教程合集

以 C++ 为实现语言,系统讲解核心数据结构与算法,涵盖链表(单链表/双链表/环检测)、栈与队列(单调栈/优先队列)、二叉树(遍历/BST/AVL/红黑树)、哈希表(开地址法/链地址法)、图(邻接表/BFS/DFS/Dijkstra/拓扑排序)、常见排序算法(快排/归并/堆排/计数排序)的实现与复杂度分析,同时分享 LeetCode 刷题技巧、竞赛编程常用模板(二分/前缀和/滑动窗口/动态规划),帮助开发者夯实算法基础。

2026.05.09

512

25

Go-Zero API开发使用教程
Go-Zero API开发使用教程

本专题聚焦Go-Zero的API开发,拆解.api描述文件的语法结构、路由与分组定义、参数绑定与校验规则,说明统一响应体、JWT鉴权、跨域与接口文档生成的落地方式,并给出网关聚合与接口测试的实践建议。

2026.11.12

140

15

Go-Zero安装与goctl环境配置教程
Go-Zero安装与goctl环境配置教程

本专题围绕Go-Zero的安装与工具链配置展开,讲清Go版本要求、goctl安装方式、代理镜像、protoc依赖与环境变量设置,说明多版本共存、升级回退与CI流水线安装的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.12

100

15

Go-Zero零基础入门教程
Go-Zero零基础入门教程

本专题整理Go-Zero的入门知识,从框架定位、环境准备到跑通第一个API服务,讲清目录分层、配置加载、日志与中间件的基本用法,并对比Gin、Kratos的差异,帮助Go开发者建立整体认知,判断它是否适合当前项目。

2026.11.12

60

15

Postman身份认证怎么配置
Postman身份认证怎么配置

本专题从实际API接口调试场景出发,讲解Postman身份认证的完整配置流程,包括常见认证协议介绍、授权参数设置、访问令牌填写、OAuth 2.0授权及认证失败排查,帮助用户正确完成接口授权与访问验证。

2026.11.06

160

12

Postman请求头Headers怎么设置
Postman请求头Headers怎么设置

围绕Postman HTTP请求头配置展开,讲解Headers选项的具体使用方式,包括Key和Value参数填写、请求头信息添加、常见Header字段设置及请求头修改方法,帮助用户解决接口调试过程中遇到的请求头配置问题。

2026.11.06

140

13

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
热门推荐
/
最新课程
phpStudy极速入门视频教程
phpStudy极速入门视频教程

共6课时 | 54.7万人学习

独孤九贱(4)_PHP视频教程
独孤九贱(4)_PHP视频教程

共89课时 | 134.3万人学习