树状数组套权值线段树

数据结构 / seg-in-bit

本地源文件：docs/ds__seg-in-bit.md

树状数组套权值线段树

静态区间 k 小值（POJ 2104 K-th Number） 的问题可以用 权值线段树 在 𝑂(𝑛log⁡𝑛)O(nlog⁡n) 的时间复杂度内解决．

如果区间变成动态的呢？即，如果还要求支持一种操作：单点修改某一位上的值，又该怎么办呢？

例题 二逼平衡树（树套树）

维护一个有序数列，其中需要提供以下操作：

  • 查询 𝑥x 在区间内的排名；
  • 查询区间内排名为 𝑘k 的值；
  • 修改某一位置上的数值；
  • 查询 𝑥x 在区间内的前驱（前驱定义为小于 𝑥x，且最大的数）；
  • 查询 𝑥x 在区间内的后继（后继定义为大于 𝑥x，且最小的数）．

例题 洛谷 P2617 Dynamic Rankings

给定一个含有 𝑛n 个数的序列 𝑎1,𝑎2…𝑎𝑛a1,a2…an，需要支持两种操作：

  • Q l r k 表示查询下标在区间 [𝑙,𝑟][l,r] 中的第 𝑘k 小的数
  • C x y 表示将 𝑎𝑥ax 改为 𝑦y

如果用 线段树套平衡树 中所论述的，用线段树套平衡树，即对于线段树的每一个节点，对于其所表示的区间维护一个平衡树，然后用二分来查找 𝑘k 小值．由于每次查询操作都要覆盖多个区间，即有多个节点，但是平衡树并不能多个值一起查找，所以时间复杂度是 𝑂(𝑛log3⁡𝑛)O(nlog3⁡n)，并不是最优的．

优化的思路是把二分答案的操作和查询小于一个值的数的数量两种操作结合起来，使用 线段树套动态开点权值线段树 ，由于所有线段树的结构是相同的，可以在多棵树上同时进行线段树上二分．

在修改操作进行时，先在线段树上从上往下跳到被修改的点，删除所经过的点所指向的动态开点权值线段树上的原来的值，然后插入新的值，要经过 𝑂(log⁡𝑛)O(log⁡n) 个线段树上的节点，在动态开点权值线段树上一次修改操作是 𝑂(log⁡𝑛)O(log⁡n) 的，所以修改操作的时间复杂度为 𝑂(log2⁡𝑛)O(log2⁡n)．

在查询答案时，先取出该区间覆盖在线段树上的所有点，然后用类似于静态区间 𝑘k 小值的方法，将这些点一起向左儿子或向右儿子跳．如果所有这些点左儿子存储的值大于等于 𝑘k，则往左跳，否则往右跳．由于最多只能覆盖 𝑂(log⁡𝑛)O(log⁡n) 个节点，所以最多一次只有这么多个节点向下跳，时间复杂度为 𝑂(log2⁡𝑛)O(log2⁡n)．

由于线段树的常数较大，在实现中往往使用常数更小且更方便处理前缀和的 树状数组 实现．另外空间复杂度是 𝑂(𝑛log2⁡𝑛)O(nlog2⁡n) 的，使用时 注意空间限制 ．

给出一种代码实现：

实现

---|---

* * *

> __本页面最近更新： 2026/1/7 08:56:54，[更新历史](https://github.com/OI-wiki/OI-wiki/commits/master/docs/ds/seg-in-bit.md)
>  __发现错误？想一起完善？[在 GitHub 上编辑此页！](https://oi-wiki.org/edit-landing/?ref=/ds/seg-in-bit.md "edit.link.title")
>  __本页面贡献者：[Ir1d](https://github.com/Ir1d), [H-J-Granger](https://github.com/H-J-Granger), [sshwy](https://github.com/sshwy), [StudyingFather](https://github.com/StudyingFather), [countercurrent-time](https://github.com/countercurrent-time), [Enter-tainer](https://github.com/Enter-tainer), [hsfzLZH1](https://github.com/hsfzLZH1), [NachtgeistW](https://github.com/NachtgeistW), [Tiphereth-A](https://github.com/Tiphereth-A), [GavinZhengOI](https://github.com/GavinZhengOI), [AngelKitty](https://github.com/AngelKitty), [CCXXXI](https://github.com/CCXXXI), [cjsoft](https://github.com/cjsoft), [diauweb](https://github.com/diauweb), [Early0v0](https://github.com/Early0v0), [ezoixx130](https://github.com/ezoixx130), [GekkaSaori](https://github.com/GekkaSaori), [Konano](https://github.com/Konano), [LovelyBuggies](https://github.com/LovelyBuggies), [Makkiy](https://github.com/Makkiy), [mgt](mailto:i@margatroid.xyz), [minghu6](https://github.com/minghu6), [ouuan](https://github.com/ouuan), [P-Y-Y](https://github.com/P-Y-Y), [PotassiumWings](https://github.com/PotassiumWings), [SamZhangQingChuan](https://github.com/SamZhangQingChuan), [Suyun514](mailto:suyun514@qq.com), [weiyong1024](https://github.com/weiyong1024), [c-forrest](https://github.com/c-forrest), [Gesrua](https://github.com/Gesrua), [Great-designer](https://github.com/Great-designer), [ksyx](https://github.com/ksyx), [kxccc](https://github.com/kxccc), [lychees](https://github.com/lychees), [Peanut-Tang](https://github.com/Peanut-Tang), [renbaoshuo](https://github.com/renbaoshuo), [SukkaW](https://github.com/SukkaW), [xyf007](https://github.com/xyf007), [ZnPdCo](https://github.com/ZnPdCo)
>  __本页面的全部内容在**[CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/deed.zh) 和 [SATA](https://github.com/zTrix/sata-license)** 协议之条款下提供，附加条款亦可能应用