二叉索引树范围更新和点查询

引言

在本文中，我们将讨论二叉索引树的区间更新和点查询。但在此之前，我们必须了解什么是二叉索引树。

我们可以说二叉索引树是一种数据结构，它帮助我们以数组的形式存储数据。借助它，我们可以计算数组元素前缀和。在这种数据结构中，我们可以将所有正数表示为 2 的幂的和。

现在，让我们举一个例子来理解区间更新和区间查询。

假设我们有一个包含 N 个整数的数组。通过这个数组，我们必须执行以下操作。

• 更新 {x, L, R}

在本节中，我们必须执行数组元素的更新操作，其索引范围从 L 到 R。之后，我们必须将 x 元素添加到其索引范围从 L 到 R 的每个元素中。此操作称为区间更新。

• 查询 {L, R}

在本节中，我们必须找到数组元素索引的和，其范围从 L 到 R。这是一个区间查询的示例。

现在，我们将借助二叉索引树执行上述两个操作。我们有一个包含 n 个元素的数组。此数组中存在的所有元素的初始值为 0。Q 表示查询的数量。

解决方案方法

在本节中，我们将解决二叉索引树中的更新和区间查询。我们可以借助前缀和来解决区间和查询。假设我们必须找到一个范围从 L 到 R 的数组的和。我们可以通过从前缀和 [0, R] 中减去前缀和 [0, L-1] 来找到这个和。我们可以借助二叉索引树在 O(log N) 时间内计算前缀和。

假设有一个区间更新查询，其范围从 L 到 R，我们必须找到范围从 0 到 M 的前缀和。

情况 1

在这种情况下，我们必须找到通过更新范围从 L 到 R 可能不会影响范围的和。

情况 2

在这种情况下，我们必须将范围的和增加到 (x*M - x*(L-1))。然后，我们必须更新范围从 L 到 R。

情况 3

在这种情况下，我们必须将范围的和增加到 (x*R - x*(L-1))。然后，我们必须更新范围从 L 到 R。

算法-

要解决此问题，我们必须遵循以下步骤。它们如下。

步骤 1

首先，我们必须编写主函数。在该主函数内部，我们必须创建存储数组和该数组中存在的元素数量的变量。之后，我们必须创建两个二叉索引，然后将该变量初始化为零。

步骤 2

现在我们必须根据查询类型调用 "rangeUpdateQuery()" 和 "rangeSumQuery()" 函数。

步骤 3

然后，我们必须创建函数 rangeSumQuery()，它接受两个参数，例如二叉树的二叉索引。此函数计算数组元素范围从 L 到 R 的和。在该函数内部，我们执行前缀和 [0, R] 和 [0, L-1]，并从前缀和 [0, R] 中减去前缀和 [0, L-1] 以获得范围 [L, R] 的所需和。

步骤 4

然后我们必须创建 rangeUpdateQuery()，它更新两个二叉索引树，使得一个二叉索引树可用于获取任何索引处的值，另一个可用于在每次更新查询后获取 (x*(L-1)) 的值。

C++ 代码实现

代码

输出

说明

在上面的代码中，我们借助 C++ 代码创建了两个函数，例如 rangeUpdateQuery() 和 rangeSumQuery()。此代码帮助我们解决上述问题。

Java 实现

代码

输出

说明

在上面的代码中，我们用 Java 实现了两种方法，例如 update() 和 getElement()。借助这两种方法，我们可以更新数组的索引，并且还可以获取更新索引值中存在的元素。

算法复杂度

时间复杂度

上述方法的时间复杂度为 O(Q * log(N))

其中，“Q” 是查询的数量，“N” 是数组中元素的数量。

空间复杂度

上述问题的时间复杂度为 O(N)。

其中，“N” 是给定数组中元素的总数。