Java 中线段树的懒惰传播

2025年5月13日 | 阅读 9 分钟

Java 中的线段树懒惰传播话题是 Java 中线段树话题的延续。建议读者先阅读线段树话题。线段树中的懒惰传播意味着推迟某些值的更新，只在需要时才更新它们。

更新操作

让我们回顾一下线段树的更新操作。

从线段树的根开始。
如果当前节点的范围不包含输入数组的索引，则返回。
否则，更新当前节点，并从步骤 2 开始为当前节点的子节点重复操作。

Lazy Propagation in Segment Tree in Java

懒惰传播的场景

让我们讨论一个应该使用懒惰传播技术的场景。

假设任务是从索引 1 到 4 的输入数组的每个元素中添加值 6。为了完成此任务，必须为索引 1 到 4 的每个元素调用 update() 方法。这些多次调用会导致更多的时间消耗。这正是懒惰传播技术发挥作用，以加快更新过程。

请注意，线段树的节点包含查询特定范围索引的结果。如果此节点的范围包含在更新操作的范围内，则必须更新该节点的所有后代。例如，如果我们考虑上面图表中值为 35 的节点，那么该节点包含索引 3 到 5 的值之和（参见上图）。如果更新的查询范围是 2 到 5，那么我们必须更新该节点及其所有后代。使用懒惰传播，我们需要更新值为 35 的节点，并通过将这些更新信息存储在称为懒惰节点或值的单独节点中来推迟其后代的更新。我们创建一个数组 lazy[] 来表示懒惰节点。数组 lazy[] 的大小与表示线段树的数组（在以下代码中为 t[]）的大小相同。

该方法是将 lazy[] 数组的所有元素初始化为 0。lazy[j] 数组中的值为 0 表示节点 j 在线段树中没有待处理的更新。lazy[j] 的任何其他值（例如 v）表示在对节点 j 进行任何查询之前，必须在线段树中向节点 j 添加 v 的金额。

使用线段树懒惰传播更新节点涉及的步骤

// To update the segment tree for changes in the array values 
// at the array indexes from x to y.
updateRange(us, ue)
1) If a node of the current segment tree has any update pending, then 
at first complete that pending update of that node
2) If the range of the current node lies completely in the range of the update query.
....i) Update the current node
....ii) Postpone the updates to child nodes by setting the lazy value for the child nodes.
3) If the range of the current node overlaps with the update range, then follow the same    
     approach as the above simple update.
...i) Recur for the left and the right children.
...ii) Update the current node using the results of the left and right calls.

懒惰传播的实现

观察下面的程序。

文件名：LazySegTree.java

// A Java program to show the lazy propagation in the segment tree
public class LazySegTree
{
final int MAX_SIZE = 100;	 // Max tree size
int t[] = new int[MAX_SIZE]; // To store segment tree
int lazy[] = new int[MAX_SIZE]; // To store pending updates
// currNode -> index of the current node in the segment tree
//	x and y -> Start and end indices of the elements for
//	                  which the current nodes keep sum.
// 	s and e -> start and end indices of the update query
//	val -> it is the value one needs to add in the range x to y
void updateRangeUtil(int currNode, int x, int y, int s, int e, int val)
{
// If the lazy value is non-zero for the current node of the segment tree, 
// then there are some updates pending. Therefore, we need to ensure that
// that the updates pending are completed before
// making any new updates. It is because the value might get used by
// the parent after the recursive calls (Observe the last statement of this
// method)
if (lazy[currNode] != 0)
{
// Make the pending updates using the value stored in the lazy nodes
t[currNode] += (y - x + 1) * lazy[currNode];
// checking if it is not leaf node because if
// it is leaf node, then we cannot go further
if (x != y)
{
// We can defer the updating of children as we do not require
// their updated values now.
// Since we are not yet updating the children of the node si,
// it is required to set the lazy flags for its children
lazy[2 * currNode + 1] += lazy[currNode];
lazy[2 * currNode + 2] += lazy[currNode];
}
// Setting the lazy value for the current node as 0 
// as it is updated
lazy[currNode] = 0;
}
// out of the range
if (x > y || x > e || y < s)
{
return;
}
// the Current segment is completely in the range
if (x >= s && y <= e)
{
// Add the difference to current node
t[currNode] += (y - x + 1) * val;
// the same logic for checking for the leaf nodes
if (x != y)
{
// It is where the values are stored in the lazy nodes,
// rather than doing the updation on the segment tree.
// Since the updated values is not needed now,
// we can defer the updates by keeping the values in the lazy[]
lazy[2 * currNode + 1] += val;
lazy[2 * currNode + 2] += val;
}
return;
}
// If not fully in the range, but there are some overlaps, 
// recur for the children,
int mid = (x + y) / 2;
updateRangeUtil(2 * currNode + 1, x, mid, s, e, val);
updateRangeUtil(2 * currNode + 2, mid + 1, y, s, e, val);
// And using the result of the children calls the  node is getting updated
t[currNode] = t[2 * currNode + 1] + t[2 * currNode + 2];
}
// Method to update a range of values in the segment tree
// x and y -> start and end indices of the update query
// val -> it is the value one needs to add in the range x to y
void updateRange(int n, int x, int y, int val) 
{
updateRangeUtil(0, 0, n - 1, x, y, val);
}
// A recursive method to find the sum of values of the given range in the array. 
// The parameters for this method are described as: 
//	si --> The current node index of the segment tree.
//		In the beginning, 0 is passed as the root and is always at'
//		the index 0
//	x & y --> Start and end indices of the segment
//				 is shown by the current node,
//				i.e., t[si]
//	s & e --> Start and end indices of the query
//				range 
int getSumUtil(int x, int y, int s, int e, int si)
{
// If the lazy flag is set for the current node of the segment tree,
// then it means that some of the updates are pending. Therefore, we need to
// ensure that the updates pending are completed before
// the processing of the sub sum query
if (lazy[si] != 0)
{
// Make the pending updates to the node. Notice that this
// node representing the sum of elements in array a[x .. y] and
// all these elements should be incremented by lazy[si]
t[si] += (y - x + 1) * lazy[si];
// checking if it is not leaf node because if
// it is leaf node then we cannot go further
if (x != y)
{
// Since we do not need the updated values now,
// we defer the updates by keeping the values in the lazy[]
lazy[2 * si + 1] += lazy[si];
lazy[2 * si + 2] += lazy[si];
}
// set the value in the array lazy[] at the index si to zero
// it is because its value is updated
lazy[si] = 0;
}
// Out of the range
if (x > y || x > e || y < s)
{
return 0;
}
// At this point, ensure that the lazy updates that were pending are finished
// for the current node. Hence, we can return the value (the same as
// it was for the query in the topic of segment tree post)

// If this segment lies in the range
if (x >= s && y <= e)
{
return t[si];
}
// If any part of the segment is overlapping
// with the given range
int mid = (x + y) / 2;
return getSumUtil(x, mid, s, e, 2 * si + 1) +
getSumUtil(mid + 1, y, s, e, 2 * si + 2);
}
// Return sum of elements in range from index x (query
// start) to y (query end). It uses the getSumUtil() method
int getSum(int s, int x, int y)
{
// Checking for the absurd input values
if (x < 0 || y > s - 1 || x > y)
{
System.out.println("Input is Invalid");
return -1;
}
return getSumUtil(0, s - 1, x, y, 0);
}
// A recursive method that constructs the Segment Tree for
// a[x ... y]. si is the index of the current node in the segment
// tree. 
void constructSTUtil(int a[], int x, int y, int si)
{
// out of the range as x can never be greater than y
if (x > y)
{
return;
}
// when there is only one element in the array, keep that element in
// the current node of the segment tree and then return
if (x == y)
{
t[si] = a[x];
return;
}
// when there is more than single elements, then do the recursion
// for the left and the right subtrees and keep the sum
// of the values in the node
int m = (x + y) / 2;
constructSTUtil(a, x, m, 2 * si + 1);
constructSTUtil(a, m + 1, y, 2* si + 2);
t[si] = t[2 * si + 1] + t[2 * si + 2];
}
// method to build the segment tree from the array a[].
// The method allocates memory for the segment tree and
// invokes the constructSTUtil() method filling the memory allocated
void constructST(int a[], int s)
{
// filling the memory allocated for st
constructSTUtil(a, 0, s - 1, 0);
}
// main method
public static void main(String argvs[])
{
int a[] = {2, 4, 7, 10, 12, 13};
int s = a.length;
// Creating an object of the class LazySegTree
LazySegTree tObj = new LazySegTree();
// Building the segment tree from the array a[]
tObj.constructST(a, s);
// Displaying the sum of the values in the array a[] from the index 1 to 4
System.out.println("The sum of the values in the given range is: " +
tObj.getSum(s, 1, 4));
// Adding the sum 7 to all of the nodes sitting at the indices from 1 to 5.
tObj.updateRange(s, 1, 5, 7);
// Finding the sum after values are getting updated
System.out.println("The sum of the values, after updation, in the given range is: " +
tObj.getSum(s, 1, 4));
}
}

输出

The sum of the values in the given range is: 33
The sum of the values, after updation, in the given range is: 61

下一个主题Final-arrays-in-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 9 接口私有方法

Java 中的找不到符号错误

Dijkstra Algorithm Java

Java 中能被 K 整除的最小整数问题

Nested Loops in Java

Java 中按逗号分割字符串

Bouncy Number in Java

Java 中的具体类

Java 中 IntSummaryStatistics getSum() 方法及示例

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器