数据结构 树状数组套主席树 结构详解

数据结构 树状数组套主席树 结构详解 😊 | Powered By HeartFireY

一、简述

主席树主要用来解决静态区间第 k k k大的问题，它本身并不支持动态修改，也就是不支持动态区间修改。

如果我们需要进行动态区间修改，那么就需要一些辅助的数据结构进行修改。这里就需要引出我们的树套树结构。本篇博客针对树状数组套主席树的结构原理进行讲解。

使用树状数组套主席树解决静态区间第 k k k大的问题，其基本思想是在根节点记录数组上建立树状数组，使得树状数组的每个节点都表示一棵主席树。那么通过树状数组就可以找到对应需要修改的主席树并对节点进行修改。

二、详解 1.结构理解

首先来看一个主席树的结构图：

我们在根节点上建立树状数组：

那么实际上存放根节点编号的 r o o t root root数组就是一个树状数组。注意上图并没有表示出实际的结构，仅是方便理解。

这里需要说明的是：所谓的在根节点上建立树状数组，实际上是嵌套在主席树建树外层的，也就是说我们会按照树状数组的的过程去执行主席树的更新操作。建树操作可以描述如下：

for(int i = 1; i > a[i];
    for(int j = i; j