2104：K-th Number——以题解码：一文掌握主席树的核心原理及实现细节（通过一天时间的研究绘图）

文章目录

• 题目大意
• 思路分析
• • 主席树简介
  • 建树实例
  • 查询实例
  • 存储问题
  • 代码剖析
  • • 预定义元素+建树
    • 更新操作
    • 查询操作
    • 离散化+各个子树的建立

题目大意

请查看题目标记](http://poj.org/problem?id=2104)
给定一个数组a[1...n]，对于每个查询Q(i,j,k)来说，请确定在区间[i,j]内第k高的数值。

请查看题目标记](http://poj.org/problem?id=2104)
给定一个数组a[1...n]，请确定在区间[i,j]内第k高的数值，并针对每个查询Q(i,j,k)执行此操作。

思路分析

最基本的方法通常是对目标区间[i,j]进行一次排序操作之后找出第k个元素的位置；然而这种方法的时间复杂度为每次操作均为 O(n\log n) 级别，并且总共的操作次数 m<5000 会导致整体时间开销较大。针对区间查询问题寻求高效解决方案的最佳途径通常是使用线段树；具体而言，在使用线段树进行区间查询时如何确定第k大的值呢？

主席树简介

也被称为函数式线段树的数据结构，在计算机科学领域中具有重要地位。

也被称为