java中的段树

---

在这篇文章中，我们将了解 Java 中的段树。

问题

考虑一个整数数组， int[] arr = {a1, a2, a3, a4, a5,….., an};

给定两种类型的查询， (i) 在第一种类型的查询中，给定两个整数，L & R，输出 给定范围内元素的总和。 (ii) 在第二种查询中，给定一个索引和一个值， 将给定索引处的数组中的值更新为给定值。

输入格式： 第一行将包含一个整数 n，即给定数组的长度。 下一行包含 N 个空格分隔的整数，它们是数组的元素。 下一行将包含查询数。 接下来的 q 行将包含 2 个空格分隔的整数，如果第一个整数是“1”，那么它将是一个范围求和查询，如果第一个整数是“2”，那么它将是一个更新查询。

输入：
8
2 6 4 -3 5 -1 6 10
3
1 2 4
2 3 3
1 2 4
输出：
6
12

这里 1 2 4 1 表示范围求和查询，所以我们需要找到从索引到 2 到 4 的元素之和。 所以答案是6 (4 + -3 + 5)

2 3 3 2 表示更新查询，所以我们将数组中的索引 3 更新为 3，所以数组会变成 2 6 4 3 5 -1 6 10

1 2 4 再次与之前相同的查询，但由于索引 3 处的值已更新，我们将得到结果为12 (4 + 3 + 5)

---

解决方案

方法——我：

• 对于第一种类型的查询，当询问给定范围的总和时，我们运行从 L 到 R 的循环，并将范围中的每个元素添加到变量中，并输出变量以给出给定范围的总和。
• 对于第二种查询，我们更新查询中给定索引处的值。 范围查询操作的复杂度是O(n)，而更新操作的复杂度是O(1)，因为我们直接到达给定的索引并更新需要恒定时间的值。
• 因此，这种方法的总体最差时间复杂度是：O(n) + O(1)

  **: O(n)**

方法——二：

我们可以在解决任何查询之前在O(n)时间内创建一个前缀 sum 数组，而不是每次循环整个数组来查找范围 sum 。此前缀和数组包含给定数组中从第 0个索引到第 i 个索引的数组的总和。这将范围总和查询的时间复杂度归结为O(1)，因为范围[L,R]的总和可以通过以下方式找到，

• rangesum = prefixsum[R] – prefixsum[L-1] {其中 L > 0} rangesum = prefixsum[R] {其中 L = 0}

• 现在对于更新查询，每当给定数组中的元素发生变化时，都会影响范围[i, arr.length()]中所有索引的前缀和。现在最差的更新时间复杂度变成了O(n)。 这种方法最差的时间复杂度将再次是：O(1) + O(n) = O(n)

  有效的方法：

  为了解决可以是点或范围的范围查询和更新，我们使用段树，它基本上是一个完整的二叉树，对于每个父节点，都有 2 个或没有子节点，它用于有效地解决范围查询和更新 O(logN)。这些范围查询可以是任何类型，例如范围总和、范围最小值、范围最大值、范围 GCD 等。它还处理点更新和范围更新，我们将在本文后面部分看到。 在本文中，我们将讨论在 O(log n) 时间复杂度中使用 Segment tree 计算 Range Sum Query 和点更新。

  • 段树的构建：

  • 段树的每个节点都包含范围 {say [L,R]} 的总和，其左子节点包含范围 [L, mid] 的总和，右子节点包含范围 [mid + 1, R]的总和其中中 = (L+R)/2。

  • 根节点包含范围[0，n]的和，即完整数组的和。
  • 随着我们不断将父节点的范围分成两半到其子节点上，一旦节点的范围仅包含一个元素，即范围为[i，i]，最终我们将无法创建更多的子节点. 因此，包含数组单个元素之和的节点，将作为其范围不可分割的叶子节点。
  • 现在所有数组元素都将出现在叶节点上，并且树中叶节点的数量将等于数组的长度。

  现在我们如何存储树？

  我们将树存储在一个数组中，其中第i 个索引处的任何父节点的左子节点的索引将存储在索引2 *i+1**处，而右节点的索引将存储在索引*2 i+2处。所有叶节点将包含给定数组的元素，这些节点的父节点将包含其左孩子和右孩子的总和。

  数组的大小是多少？ 要回答这个问题，我们首先需要知道，完整的树中有多少个节点。 让我们考虑一个长度等于 2 的完美幂的数组，以便更清楚地理解它。

  int[] arr = {2, 6, 4, -3, 5, -1, 6, 10}

  与每个下一级一样，当前级别的每个节点都拆分为两个节点，因此下一级的节点将是当前级别的节点的两倍。 第 0 级将包含 2^0 即 1 个节点，即根节点。 第一级将包含2^1 个节点。 第二级将包含2^2 个节点。 第三级将包含2^3 个节点。

  因此，节点总数 = 2^0 + 2^1 + 2^2 + ...。+ 2^height = 2^(height+1) – 1 { sum of a GP} 我们知道， 树的高度 = log(n)到底数 2。 其中，n = 给定数组的大小。

  因此，节点总数 = 2^((log n) +1) – 1。 当我们将树的每个节点存储在一个数组中时，因此，

  段数组的大小将为 2^((log n) +1) – 1。

  int[] segArr = new int[2^((log n) +1) – 1];

  ### 建造 ：

  1. 我们从根节点开始深入递归，我们在后序中设置值，即在我们设置其子节点的值之后。
  2. 对于任何节点，我们通过将段数组的指针分别递增到 2idx+1 和 2idx+2 来调用它的左右两个子节点，我们还将每个子节点的段长度减少到其父节点范围的一半。
  3. 每当我们遇到一个叶子节点，当我们有左限制 = 右限制时，我们直接将存在的值放在给定数组的左/右（因为它们对于叶子来说都是相等的，我们可以使用它们中的任何一个）在当前段数组中的索引。这将是我们的基本情况，我们将在设置后返回此叶节点的值。
  4. 在内部节点的情况下，其值将通过将其两个子节点的值相加来按后序计算。

  ### 范围求和查询：

  每当我们得到一个查询来找出给定范围的总和时（比如 [query_left, query_right]）。 我们牢记这三点： （i）如果查询范围完全位于我们当前所在的当前节点的段之外，我们返回一个值，这样它不会对我们的最终答案做出任何贡献，因为被问到的答案范围位于其他一些节点中。 (ii) 如果查询范围完全位于当前段的范围内，则我们返回该段的完整值，因为该段将为所询问的范围查询贡献所有内容。 (iii) 如果当前节点的段和查询范围有任何重叠，我们调用它的两个子节点，因为当前段将有助于最终答案但不完全。

  ### 更新：

  在更新中，我们将需要更新给定数组中索引处的值。 我们从根节点开始搜索包含请求索引值的叶节点。然后在后序中，我们更正所有那些在其段范围内包含更新索引的节点的值。

  package org.arpit.java2blog;
  
  import java.util.Scanner;
  
  public class SegmentTree {
  
      static int[] segArr;
  
      public static void main(String[] args) {
  
          Scanner scn = new Scanner(System.in);
          int[] arr = new int[scn.nextInt()];
  
          // array on which operations / queries will be performed.
          for (int i = 0; i  0) {
              int check = scn.nextInt();
  
              if (check == 1) {
                  int ql = scn.nextInt();
                  int qr = scn.nextInt();
  
                  System.out.println(getQuery(0, 0, arr.length - 1, ql, qr, arr));
              } else {
  
                  int idx = scn.nextInt();
                  int value = scn.nextInt();
                  update(value, idx, 0, 0, arr.length - 1, arr);
  
              }
          }
  
      }
  
      public static int construct(int saIdx, int left, int right, int[] arr) {
          /*
           * if the segment is of length one, then we know it will be
           * a left node and hence it will contain an element of the given array
           */
          if (left == right) {
              /*
               * element at the current index of segArr will be the element
               * present at index left or right in given array,
               * as left is equal to right so we can take either of them
               */
              return segArr[saIdx] = arr[left];
          }
  
          /*
                  * current segment of parent node is divided into two halves,
           * if the segment for parent is [left, right], then
           * segment for left child will be [left, mid] and
           * segment for right child will be [mid+1, right].
           */
          int mid = (left + right) / 2;
          int leftChild = construct(2 * saIdx + 1, left, mid, arr);
          int rightChild = construct(2 * saIdx + 2, mid + 1, right, arr);
          /*
           * result of the current node will be calculated
           * in the post order after calculating
           *  the result for its children
           */
          segArr[saIdx] = leftChild + rightChild;
          return segArr[saIdx];
      }
  
      // saIdx - pointer for the segment array.
      // left - left limit of the current segment.
      // right - right limit of the current segment.
      // ql - left limit of the given query segment.
      // qr - right limit of the given query segment.
  
      public static int getQuery(int saIdx, int left, int right, int ql, int qr, int[] arr) {
               * if the range of the query lies completely outside the range of
           * the current segment, we return a value which contributes nothing
           * to the final answer,that 0 in the case when sum is to be calculated for given range.
           */
          if (left > qr || right = ql && right <= qr) {
              return segArr[saIdx];
          } else {
              /*
               * if there is an overlap in the segments of the query and the node,
               * then we recur for both of its children, as there will be a contribution
               * in result from both of the sides.
               */
              int mid = (left + right) / 2;
              int leftResult = getQuery(2 * saIdx + 1, left, mid, ql, qr, arr);
              int rightResult = getQuery(2 * saIdx + 2, mid + 1, right, ql, qr, arr);
              return leftResult + rightResult;
          }
  
      }
  
      public static void update(int value, int idx, int saIdx, int left, int right, int[] arr) {
          /*
           * if the index lies outside the range of the current segment
           * then there is no need for an update/call at that index,
           * so simply ret
                  if (idx  right) {
              return;
          }
          /*
           * if we found the index to be updated, we update the given array
           * as well as the segment array that is the node which has the
           * segment equal to given index.
           */
          if (idx == left && idx == right) {
              arr[left] = value;
              segArr[saIdx] = value;
              return;
          }
          /*
           * now in post order we need to update all the nodes
           *  which contains the given index in their segment
           */
          else {
              int mid = (left + right) / 2;
              update(value, idx, 2 * saIdx + 1, left, mid, arr);
              update(value, idx, 2 * saIdx + 2, mid + 1, right, arr);
  
              segArr[saIdx] = segArr[2 * saIdx + 1] + segArr[2 * saIdx + 2];
          }
      }
  
  }

  当你运行上面的程序时，你会得到下面的输出：

  8
  2 6 4 -3 5 -1 6 10
  3
  1 2 4
  2 3 3
  1 2 4
  输出：
  612

这就是java中的段树

---

原文链接：https://codingdict.com/

---