数据结构中的区间树

在本节中，我们将了解什么是区间树。在讨论之前，让我们看一个问题。

假设我们有一个数组 arr[0,…,n-1]，我们可以执行以下操作 −

  • 查找从索引 l 到 r 的元素的和，其中 0 ≤ l ≤ r ≤ n-1

  • 将数组中指定元素的值更改为新值 x。我们需要执行 arr[i] = x。i 的范围为 0 到 n – 1。

我们可以使用区间树来解决此问题。区间树可以帮助我们在 O(log n) 时间内获取和并进行查询。因此，让我们看看如何表示这一点 −

  • 叶节点是给定数组的元素

  • 每个内部节点都表示叶节点的某些合并。合并可能在不同情况下有所不同。此处合并是节点下叶的和。

假设我们有一个类似 [1, 3, 5, 7, 9, 11] 的数组。因此，区间树将是

更新于：2020-08-11

405 次浏览

开启您的 职业

完成教程获得认证

开始
广告