如何在Python中实现支持范围查询的树状数组结构

轻敏君_1221

轻敏君_1221

2026-09-22

177人浏览

原创

树状数组天然支持范围求和查询,通过两次前缀和相减实现;但不支持区间最值查询,因最大值无逆元;Python实现需注意1-based存储、0-based接口转换及离散化处理。

如何在python中实现支持范围查询的树状数组结构

树状数组本身不直接支持范围查询?先厘清概念

树状数组(Fenwick Tree)原生只支持单点更新 + 前缀和查询(即 query(i) 返回 arr[0..i] 的和),但「范围查询」如 sum(l, r) 可以通过两次前缀和相减得到:query(r) - query(l-1)。所以它**天然支持范围求和查询**,无需改造结构——关键在于你是否正确实现了前缀和接口,以及是否处理了边界(比如 l=0 时 query(-1) 要返回 0)。

Python 实现中容易出错的三个细节

用 Python 写 Fenwick Tree 时,下标习惯和负索引容易引发隐性 bug:

  • 务必使用 1-based 索引内部存储:即 tree[1] 对应原数组第 0 个元素,避免 0 & -0 运算崩溃
  • query(i) 中的 i 是原数组的右闭下标(0-based),内部要转成 i+1 后再进循环;否则 query(0) 会跳过更新
  • update(i, delta) 同理:传入 0-based 下标 i,内部从 idx = i + 1 开始向上更新

示例片段:

class Fenwick:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)  # 1-based
<pre class="brush:python;toolbar:false;">def update(self, i, delta):  # i is 0-based
    idx = i + 1
    while idx 

想查区间最值?别硬改树状数组

树状数组的更新/查询逻辑依赖「可逆运算」(如加法有减法逆元),而最大值(max)没有通用逆元——max(a,b,c) - max(a,b) 无法还原 c。所以:

Python 环境工具基础版
Python 环境工具基础版

管理 Python 项目环境,支持虚拟环境创建、依赖安装与环境诊断

下载
  • 不要尝试用标准 Fenwick Tree 支持 range_max 或 range_min
  • 需要区间最值,请换用线段树(Segment Tree)或 Sparse Table(静态场景)
  • 若坚持用类树状结构,可考虑 Binary Indexed Tree for RMQ,但它仅支持点更新 + 区间查询,且实现复杂、常数大,Python 中性能反而不如朴素遍历小数组

动态开点 or 离散化?看输入规模再决定

原始 Fenwick Tree 要求数组长度已知且固定。遇到坐标很大但实际修改点稀疏的情况(例如更新位置 10**9),不能直接开 [0] * (10**9 + 1):

  • 离散化是首选:收集所有出现过的下标(含查询和更新的 l, r, i),排序去重后映射到 0..m-1,再建大小为 m 的树状数组
  • 动态开点(字典模拟树)可行但不推荐:用 dict 存非零节点,虽省空间,但每次 query 需要沿路径检查键是否存在,逻辑臃肿且失去 O(log n) 稳定性
  • Python 中若 n ,直接离散化 + 标准实现足够快;超过 10**6 才需谨慎压常数(比如用 array.array('i') 替代 list)

离散化核心就两行:xs = sorted(set(all_positions)),然后用 bisect_left(xs, x) 查坐标。

树状数组的“范围查询”本质是前缀和差分,不是结构扩展;真正卡住人的永远是下标转换和离散化时机——写完先用 l=0, r=0 和 l=0, r=n-1 两个极端 case 跑一遍。

Python免费学习笔记(深入):立即使用
在学习笔记中,你将探索 Python 的核心概念和高级技巧!

相关文章

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

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

下载

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

相关专题

更多
python打包成可执行文件
python打包成可执行文件

本专题为大家带来python打包成可执行文件相关的文章,大家可以免费的下载体验。

2023.07.20

1931

4

python能做什么
python能做什么

python能做的有:可用于开发基于控制台的应用程序、多媒体部分开发、用于开发基于Web的应用程序、使用python处理数据、系统编程等等。本专题为大家提供python相关的各种文章、以及下载和课程。

2023.07.25

5484

7

format在python中的用法
format在python中的用法

Python中的format是一种字符串格式化方法,用于将变量或值插入到字符串中的占位符位置。通过format方法,我们可以动态地构建字符串,使其包含不同值。php中文网给大家带来了相关的教程以及文章,欢迎大家前来阅读学习。

2023.07.31

1889

3

python教程
python教程

Python已成为一门网红语言,即使是在非编程开发者当中,也掀起了一股学习的热潮。本专题为大家带来python教程的相关文章,大家可以免费体验学习。

2023.08.03

33417

23

python环境变量的配置
python环境变量的配置

Python是一种流行的编程语言,被广泛用于软件开发、数据分析和科学计算等领域。在安装Python之后,我们需要配置环境变量,以便在任何位置都能够访问Python的可执行文件。php中文网给大家带来了相关的教程以及文章,欢迎大家前来学习阅读。

2023.08.04

3927

5

python eval
python eval

eval函数是Python中一个非常强大的函数,它可以将字符串作为Python代码进行执行,实现动态编程的效果。然而,由于其潜在的安全风险和性能问题,需要谨慎使用。php中文网给大家带来了相关的教程以及文章,欢迎大家前来学习阅读。

2023.08.04

3927

5

scratch和python区别
scratch和python区别

scratch和python的区别:1、scratch是一种专为初学者设计的图形化编程语言,python是一种文本编程语言;2、scratch使用的是基于积木的编程语法,python采用更加传统的文本编程语法等等。本专题为大家提供scratch和python相关的文章、下载、课程内容,供大家免费下载体验。

2023.08.11

1283

5

python合并两个列表
python合并两个列表

Python是一种强大的编程语言,具有许多方便的功能和工具。在Python中,有多种方法可以合并两个列表。php中文网给大家带来了相关的教程以及文章,欢迎大家前来学习阅读。

2023.08.10

636

4

python是前端还是后端
python是前端还是后端

Python属于前端也属于后端,其灵活性和丰富的生态系统使得开发人员能够在不同的领域中灵活运用。本专题为大家提供python相关的文章、下载、课程内容,供大家免费下载体验。

2023.08.11

3043

5

热门下载

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

精品课程

更多
相关推荐
/
热门推荐
/
最新课程