partition tree的意思|示意

美 / pɑ:ˈtiʃən tri: / 英 / pɑrˈtɪʃən tri /

划分树

partition tree的用法详解

Partition Tree（划分树）是一种基于分治策略的数据结构，它适用于一些数值问题的求解。Partition Tree 可以在 $O(n log n)$ 的时间内预处理一维数列，然后可以在 $O(log n)$ 的时间内回答一些常见的区间查询问题，比如区间第 $k$ 大，区间中位数等等。Partition Tree 在算法竞赛中十分常用，是值得深入学习的经典数据结构之一。

Partition Tree 的基本思想是，将原数列不断划分成一些子区间，使得每个子区间都能够进行快速的统计查询。类似于线段树，Partition Tree 也是一棵完全二叉树，每个节点代表着原数列的一个区间。

在进行划分时，Partition Tree 每次都选择当前区间中的中位数（或者任意其他的分界值）将当前区间分割成两个子区间：左子树表示区间中所有小于等于中位数的数，右子树表示区间中所有大于中位数的数。这里需要注意的是，每个区间的中位数是需要排序后再找到的，因此预处理的时间复杂度是 $O(n log n)$。

在进行查询时，可以通过递归地查找 Partition Tree 上与待查询区间完全包含的节点，来最终得到答案。该过程的时间复杂度为 $O(log n)$，因为 Partition Tree 可以看成一棵二叉查找树，每次查询都可以进入子树内继续查找，总查询次数最多为树的深度。

总之，Partition Tree 是一种十分有用的数据结构，可以解决一些区间查询问题，同时也是算法竞赛中常用的技巧和优化手段之一。

partition tree相关短语

1、 binary partition tree 二叉划分树

2、 partition-tree 划分树

3、 Optimal-partition-tree 最优划分树

4、 spatial partition tree 空间划分树

5、 recursive partition-tree 递归分类树

6、 binary space partition tree 二叉树

7、 Tree Delay Optimal Partition 树最优延迟分解,和树最优延迟分解

8、 tree partition 树划分

9、 tree partition number 树划分数

partition tree相关例句

It also generates the device tree specific to the partition.

它还可以生成特定于该分区的设备树。

In this algorithm, dynamic programming is used to calculate optimal local cosine tree during the LCT for signals, and the optimal entropy code is gained by the best partition of time axes.

算法对信号进行局部余弦变换时采用动态规划算法计算最佳局部余弦树，通过获得信号在时间轴上的最佳划分来获得信号的最优嫡编码。

Each device tree has only devices assigned to that partition.