Java 中的线段树

2025年5月12日 | 阅读 8 分钟

线段树也是一种二叉树，但它用于以更好的时间复杂度解决特定问题。与堆类似，Java 中的线段树也通过数组来表示。

使用线段树的场景

让我们来了解一下线段树在哪些场景下非常有用。

假设我们有一个数组 a[] = {0, 1, …, n - 1}；并且需要在此数组上执行两项任务。这些任务是：

计算从索引 x 到 y 的元素之和，其中 0 <= x <= y <= n - 1
将数组 a[] 的一个元素的值更改为新值 p，即，需要执行 a[j] = p，其中 0 <= j <= n - 1。

让我们讨论解决上述任务的各种方法。

朴素方法

完成这些任务很容易。我们可以从索引 x 到 y 运行一个 for 循环，并计算位于索引 x 到 y 之间的元素之和。如果我们分析求和的时间复杂度，我们将得到 O(n) 时间。

另外，要更新第 j 个索引的值，可以执行 a[j] = p，此操作需要 O(1) 时间。因此，完成这两项任务的总时间复杂度为 O(n) + O(1) = O(n)。

另一种方法

另一种方法是提前创建一个前缀数组，然后完成上述任务。创建前缀数组后，从索引 x 到 y 的元素之和需要 O(1) 时间。但是，第 j 个索引的更新将需要 O(n) 时间。这是因为任何索引的更新都会影响前缀数组，而更新需要 O(1) 时间。因此，总时间复杂度为 O(1) + O(n) = O(n)，与朴素方法相同。

由于这两种方法的总体时间复杂度保持不变，因此我们需要找到一种方法来降低其时间复杂度，而这种方法就是使用线段树。线段树需要 O(log(n)) 时间来计算从索引 x 到 y 的和。对于第 j 个索引处值的更新，线段树需要 O(log(n)) 时间。因此，总体时间复杂度变为 O(log(n)) + O(log(n)) = O(2 *(log(n)))，这小于 O(n)。

线段树的表示

叶子节点代表数组中的元素。
树的内部节点由合并其子节点生成。由于我们使用数组来表示线段树，位于索引 j 的节点在 2 * j + 1 处有左子节点，在 2 * j + 2 处有右子节点，而索引 j 处节点的父节点是 ⌊(j - 1) / 2⌋。

因此，对于数组 a[] = {2, 4, 7, 10, 12, 13}，线段树在数组中的表示将是

segArr[] = {48, 13, 35, 6, 7, 22, 13, 2, 4, k, k, 10, 12, k, k}，其中 k 是虚拟值。虚拟值没有用。事实上，由于数组表示，这会浪费一些空间。

线段树将是

红色节点（叶子节点）代表数组中的元素，而橙色节点是合并其子节点的结果。

线段树表示中数组的大小

如果输入数组的大小是 2 的幂，则没有虚拟节点。因此，线段树的大小为 (2 * n - 1)，其中 n 是输入数组的大小。这是因为叶子节点的总数为 s，内部节点为 n - 1。因此，n + n - 1 = 2 * n - 1 是数组的总大小。

如果输入数组的大小不是 2 的幂，则线段树的大小为 2 * y - 1，其中 y 是大于 n 的最小的 2 的幂。例如，如果 n 的值为 9，则大于 9 的最小的 2 的幂是 16。所以 y 是 16。

给定范围求和的伪代码

构建线段树后，挑战在于使用线段树计算和。以下伪代码解决了这个问题。

int getSum(nde, x, y) 
{
   if (the range of the node is within x and y)
        return value of the node
   else if (the range of the node is outside of x and y)
        return 0
   else
    return getSum(nde left child, x, y) + 
           getSum(nde right child, x, y)
}

更新线段树中的值

线段树中的更新操作是递归完成的。假设需要更新第 j 个索引，值为 val。从线段树的根开始，将值 val 添加到其范围包含给定范围的所有节点中。如果给定节点的范围不包含给定索引，则不应对该节点进行任何更改。

线段树的实现

下面的程序展示了线段树的实现。

文件名：SegTree.java

// A Java Program that shows the segment tree operations like construction, query and 
// update
public class SegTree
{
int stArr[]; // The array that keeps the nodes of the segment tree
// Constructor to generate the segment tree from the given array. 
// The constructor allocates memory for the segment tree and invokes
// the method constructST() to fill the memory allocated
SegTree(int a[], int s)
{
// Allocate memory for segment tree
//Height of segment tree
int h = (int) (Math.ceil(Math.log(s) / Math.log(2)));
//Maximum size of segment tree
int maxSize = 2 * (int) Math.pow(2, h) - 1;
// for allocatiing the memory for the array 
// that represents the segment tree
stArr = new int[maxSize]; constructST(a, 0, s - 1, 0);
}
// A utility method to find the middle index from the corner indices.
int getMidIndex(int f, int l) 
{
return f + (l - f) / 2;
}
// A recursive method to find the sum of the values in the given range
// of the given array. The following are the parameters for the method.

// stArr --> The array representing the segment tree
// si --> Index of the current node in the segment tree. 
// Initially, 0 is passed as the root is always at the index 0
// x & y --> Start and end indices of the segment represented
//				by the current node, i.e., stArr[si]
// i & j --> Start and end indices of the query range
int getSumUtil(int x, int y, int i, int j, int si)
{
// If the segment of the node is the part of the given range, 
// then return the sum of the segment
if (i <= x && j >= y)
{
return stArr[si];
}
// If the segment of the node is outside of the given range
if (y < i || x > j)
{
return 0;
}

// If a part of the segment overlaps with the range given
int midVal = getMidIndex(x, y);
return getSumUtil(x, midVal, i, j, 2 * si + 1) +
	getSumUtil(midVal + 1, y, i, j, 2 * si + 2);
}
// A recursive method to update the nodes that have the given
// index in their range. The following are the parameters
//	si, x and y are same as the getSumUtil() method
//	j --> index of the element to be updated. The index is in
//	      the input array.
// val --> Value that has to be added to all of the nodes which have j in the range 
void updateValUtil(int x, int y, int j, int val, int si)
{
// Base Case: If the input index lies outside the range of
// this segment
if (j < x || j > y)
{
return;
}
// If the range of the node contains the input index, then update the
// value of the node and its children
stArr[si] = stArr[si] + val;
if (y != x) 
{
int midVal = getMidIndex(x, y);
updateValUtil(x, midVal, j, val, 2 * si + 1);
updateValUtil(midVal + 1, y, j, val, 2 * si + 2);
}
}
// The method is to update the value in the input array and the segment tree.
// It uses the updateValUtil() to update the value in the segment tree
void updateVal(int a[], int s, int j, int newVal)
{
// Check for erroneous input index
if (j < 0 || j > s - 1) 
{
System.out.println("Input is Invalid");
return;
}
// Get the difference between the old value and new value
int diffVal = newVal - a[j];
// Update the value in array
stArr[j] = newVal;
// Update the values of nodes in segment tree
updateValUtil(0, s - 1, j, diffVal, 0);
}
// Returning the sum of elements in the range from the index x (query start) to
// y (query end). It uses the method getSumUtil()
int getSum(int s, int x, int y)
{
// Checking for the absurd input values
if (x < 0 || x > s - 1 || x > y) 
{
System.out.println("The input is invalid");
return -1;
}
return getSumUtil(0, s - 1, x, y, 0);
}
// A recursive method that does the construction of the Segment Tree for the array 
// a[x ... y].
// si is the index of the current node in the segment tree stArr
int constructST(int a[], int x, int y, int si)
{
// If only one element is present in the array, store it 
// in the current node of the segment tree and then return
if (x == y) 
{
stArr[si] = a[x];
return a[x];
}
// If there are more than one element, then apply recurrence in the left and
// right subtrees and the store the sum of values in this node
int mid = getMidIndex(x, y);
stArr[si] = constructST(a, x, mid, si * 2 + 1) +
	constructST(a, mid + 1, y, si * 2 + 2);
return stArr[si];
}
// Main method
public static void main(String argvs[])
{
// input array
int a[] = {2, 4, 7, 10, 12, 13};
int size = a.length; // size of the input array
// Building the segment tree from the input array
SegTree tree = new SegTree(a, size);
// Printing the sum of values in the input array from index 1 to 4
System.out.println("Sum of values in the given range 1 to 4 = " + tree.getSum(size, 1, 4));
// Update: setting arr[3] = 11 and updating the corresponding segment
// of the tree nodes
tree.updateVal(a, size, 3, 11);
// Finding the sum after the value is getting updated
System.out.println("Updated sum of values in the given range = " + tree.getSum(size, 1, 4));
}
}

输出

Sum of values in the given range 1 to 4 = 33
Updated sum of values in the given range = 34

下一主题交通灯程序（Java）

Java 中的线段树

使用线段树的场景

朴素方法

另一种方法

线段树的表示

线段树表示中数组的大小

给定范围求和的伪代码

更新线段树中的值

线段树的实现

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中的线段树

使用线段树的场景

朴素方法

另一种方法

线段树的表示

线段树表示中数组的大小

给定范围求和的伪代码

更新线段树中的值

线段树的实现

相关帖子

Java 中计算所有元素的子矩阵

在 Java 中交换字符串中的字符对

Java 中的回文分割问题

Merge Two Sorted Linked Lists in Java

Java 类的静态实例

Java 中的 Zygodromes

Peterson Number in Java

Java XOR

Java 9 Optional 类改进

使用数组在 Java 中反转字符串

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器