线段树中的懒惰传播

2025年03月17日 | 阅读 9 分钟

在上篇文章中，我们介绍了线段树及其范围求和问题的示例。我们使用相同的“指定范围求和”问题解释了懒惰传播。

简单的线段树更新函数是如何工作的？

在上一节中，update 方法用于仅更改数组中的一个值。由于一个数组元素可能位于多个线段树节点的范围内，因此需要注意，数组中单个值的更新可能会导致线段树中出现多个更新。

本文中的简单推理如下所示。

1) 从线段树的根节点开始。

2) 如果需要修改的数组索引超出了当前节点的范围，则返回。

3) 更新当前节点，如果不是，则对子节点重复此操作。

此处显示了上一篇文章中的代码。

C++ 代码

上述策略的应用如下所示：

/* A recursive function to update the nodes which have the given
index in their range. The following are parameters
	tree[] --> segment tree
	si	 --> index of current node in segment tree.
				Initial value is passed as 0.
	ss and se --> Starting and ending indexes of array elements
				covered under this node of segment tree.
				Initial values passed as 0 and n-1.
	i --> index of the element to be updated. This index
			is in input array.
diff --> Value to be added to all nodes which have array
			index i in range */
void updateValueUtil(int tree[], int ss, int se, int i,
					int diff, int si)
{
	// Base Case: If the input index lies outside the range
	// of this segment
	if (i < ss || i > se)
		return;

	// If the input index is in range of this node, then
	// update the value of the node and its children
	st[si] = st[si] + diff;
	if (se != ss)
	{
		int mid = getMid(ss, se);
		updateValueUtil(st, ss, mid, i, diff, 2*si + 1);
		updateValueUtil(st, mid+1, se, i, diff, 2*si + 2);
	}
}

如果许多数组索引需要更新怎么办？

例如，将索引在 2 到 7 之间的每个数组元素增加 10。对于从 2 到 7 的每个索引，必须调用上述更新。通过创建一个名为 updateRange() 的函数来根据需要更新节点，我们可以避免进行多次调用。

C++ 代码

上述策略的应用如下所示：

/* Function to update segment tree for range update in input
array.
	si -> index of current node in segment tree
	ss and se -> Starting and ending indexes of elements for
				which current nodes stores sum.
	us and ue -> starting and ending indexes of update query
	diff -> which we need to add in the range us to ue */
void updateRangeUtil(int si, int ss, int se, int us,
					int ue, int diff)
{
	// out of range
	if (ss>se || ss>ue || se<us)
		return ;

	// Current node is a leaf node
	if (ss==se)
	{
		// Add the difference to current node
		tree[si] += diff;
		return;
	}

	// If not a leaf node, recur for children.
	int mid = (ss+se)/2;
	updateRangeUtil(si*2+1, ss, mid, us, ue, diff);
	updateRangeUtil(si*2+2, mid+1, se, us, ue, diff);

	// Use the result of children calls to update this
	// node
	Tree [si] = tree [si*2+1] + tree [si*2+2];
}

懒惰传播是一种用于加快范围更新速度的优化技术。

当存在多个更新且正在对范围执行更新时（避免在更新中进行递归调用），我们可以延迟一些更新，并在需要时才执行这些更新。

请注意，线段树中的一个节点存储或表示多个索引的查询结果。此外，如果更新操作的范围包含该节点，则其所有后代也必须更新。例如，考虑上图中值为 27 的节点。此节点包含索引 3 到 5 之间的值的总和。如果我们的更新查询涵盖范围 2 到 5，我们必须同时更新此节点及其所有后代。

通过将此更新信息存储在称为懒惰节点或值的独立节点中，我们可以仅更新值为 27 的节点，并延迟对其后代的更新。我们创建了一个名为 lazy[] 的数组来代表懒惰节点。lazy[] 的大小与用于表示线段树的代码中的数组相同，即 tree[]。

目标是将 lazy[] 的所有元素设置为 0。如果 lazy[i] 的值为 0，则表示线段树节点 i 上没有待处理的更改。lazy[i] 的非零值表示在对线段树节点 i 进行任何查询之前，必须将此总和添加到该节点。

这是更新后的更新技术。

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

查询函数是否也已更改？

如果查询发送到一个尚未更新的节点，可能会出现问题，因为我们修改了 update 以推迟其活动。因此，我们还需要修改上一篇文章中使用的查询方法 getSumUtil。getSumUtil() 现在在更新节点之前确定是否有待处理的更新。一旦它确认所有待处理的更新都已完成，它的功能就与之前的 getSumUtil() 类似。

下面的程序展示了懒惰传播的工作原理。

C++ 代码

上述策略的应用如下所示：

// Program to show segment tree to demonstrate lazy
// propagation
#include <stdio.h>
#include <math.h>
#define MAX 1000

// Ideally, we should not use global variables and large
// constant-sized arrays, we have done it here for simplicity.
int tree[MAX] = {0}; // To store segment tree
int lazy[MAX] = {0}; // To store pending updates

/* si -> index of current node in segment tree
	ss and se -> Starting and ending indexes of elements for
				which current nodes stores sum.
	us and ue -> starting and ending indexes of update query
	diff -> which we need to add in the range us to ue */
void updateRangeUtil(int si, int ss, int se, int us,
					int ue, int diff)
{
	// If lazy value is non-zero for current node of segment
	// tree, then there are some pending updates. So we need
	// to make sure that the pending updates are done before
	// making new updates. Because this value may be used by
	// parent after recursive calls (See last line of this
	// function)
	if (lazy[si] != 0)
	{
		// Make pending updates using value stored in lazy
		// nodes
		tree[si] += (se-ss+1)*lazy[si];

		// checking if it is not leaf node because if
		// it is leaf node then we cannot go further
		if (ss != se)
		{
			// We can postpone updating children we don't
			// need their new values now.
			// Since we are not yet updating children of si,
			// we need to set lazy flags for the children
			lazy[si*2 + 1] += lazy[si];
			lazy[si*2 + 2] += lazy[si];
		}

		// Set the lazy value for current node as 0 as it
		// has been updated
		lazy[si] = 0;
	}

	// out of range
	if (ss>se || ss>ue || se<us)
		return ;

	// Current segment is fully in range
	if (ss>=us && se<=ue)
	{
		// Add the difference to current node
		tree[si] += (se-ss+1)*diff;

		// same logic for checking leaf node or not
		if (ss != se)
		{
			// This is where we store values in lazy nodes,
			// rather than updating the segment tree itself
			// Since we don't need these updated values now
			// we postpone updates by storing values in lazy[]
			lazy[si*2 + 1] += diff;
			lazy[si*2 + 2] += diff;
		}
		return;
	}

	// If not completely in rang, but overlaps, recur for
	// children,
	int mid = (ss+se)/2;
	updateRangeUtil(si*2+1, ss, mid, us, ue, diff);
	updateRangeUtil(si*2+2, mid+1, se, us, ue, diff);

	// And use the result of children calls to update this
	// node
	tree[si] = tree[si*2+1] + tree[si*2+2];
}

// Function to update a range of values in segment
// tree
/* us and eu -> starting and ending indexes of update query
	ue -> ending index of update query
	diff -> which we need to add in the range us to ue */
void updateRange(int n, int us, int ue, int diff)
{
updateRangeUtil(0, 0, n-1, us, ue, diff);
}


/* A recursive function to get the sum of values in given
	range of the array. The following are parameters for
	this function.
	si --> Index of current node in the segment tree.
		Initially 0 is passed as root is always at'
		index 0
	ss & se --> Starting and ending indexes of the
				segment represented by current node,
				i.e., tree[si]
	qs & qe --> Starting and ending indexes of query
				range */
int getSumUtil(int ss, int se, int qs, int qe, int si)
{
	// If lazy flag is set for current node of segment tree,
	// then there are some pending updates. So we need to
	// make sure that the pending updates are done before
	// processing the sub sum query
	if (lazy[si] != 0)
	{
		// Make pending updates to this node. Note that this
		// node represents sum of elements in arr[ss..se] and
		// all these elements must be increased by lazy[si]
		tree[si] += (se-ss+1)*lazy[si];

		// checking if it is not leaf node because if
		// it is leaf node then we cannot go further
		if (ss != se)
		{
			// Since we are not yet updating children os si,
			// we need to set lazy values for the children
			lazy[si*2+1] += lazy[si];
			lazy[si*2+2] += lazy[si];
		}

		// unset the lazy value for current node as it has
		// been updated
		lazy[si] = 0;
	}

	// Out of range
	if (ss>se || ss>qe || se<qs)
		return 0;

	// At this point we are sure that pending lazy updates
	// are done for current node. So we can return value
	// (same as it was for query in our previous post)

	// If this segment lies in range
	if (ss>=qs && se<=qe)
		return tree[si];

	// If a part of this segment overlaps with the given
	// range
	int mid = (ss + se)/2;
	return getSumUtil(ss, mid, qs, qe, 2*si+1) +
		getSumUtil(mid+1, se, qs, qe, 2*si+2);
}

// Return sum of elements in range from index qs (query
// start) to qe (query end). It mainly uses getSumUtil()
int getSum(int n, int qs, int qe)
{
	// Check for erroneous input values
	if (qs < 0 || qe > n-1 || qs > qe)
	{
		printf("Invalid Input");
		return -1;
	}

	return getSumUtil(0, n-1, qs, qe, 0);
}

// A recursive function that constructs Segment Tree for
// array[ss..se]. si is index of current node in segment
// tree st.
void constructSTUtil(int arr[], int ss, int se, int si)
{
	// out of range as ss can never be greater than se
	if (ss > se)
		return ;

	// If there is one element in array, store it in
	// current node of segment tree and return
	if (ss == se)
	{
		tree[si] = arr[ss];
		return;
	}

	// If there are more than one elements, then recur
	// for left and right subtrees and store the sum
	// of values in this node
	int mid = (ss + se)/2;
	constructSTUtil(arr, ss, mid, si*2+1);
	constructSTUtil(arr, mid+1, se, si*2+2);

	tree[si] = tree[si*2 + 1] + tree[si*2 + 2];
}

/* Function to construct segment tree from given array.
This function allocates memory for segment tree and
calls constructSTUtil() to fill the allocated memory */
void constructST(int arr[], int n)
{
	// Fill the allocated memory st
	constructSTUtil(arr, 0, n-1, 0);
}


// Driver program to test above functions
int main()
{
	int arr[] = {1, 3, 5, 7, 9, 11};
	int n = sizeof(arr)/sizeof(arr[0]);

	// Build segment tree from given array
	constructST(arr, n);

	// Print sum of values in array from index 1 to 3
	printf("Sum of values in given range = %d\n",
		getSum(n, 1, 3));

	// Add 10 to all nodes at indexes from 1 to 5.
	updateRange(n, 1, 5, 10);

	// Find sum after the value is updated
	printf("Updated sum of values in given range = %d\n",
			getSum( n, 1, 3));

	return 0;
}

输出

Sum of values in given range = 15
Updated sum of values in given range = 45

时间复杂度：O(n)

辅助空间： O(MAX)

下一主题线段树 - 范围最小值查询

线段树中的懒惰传播

简单的线段树更新函数是如何工作的？

C++ 代码

如果许多数组索引需要更新怎么办？

C++ 代码

懒惰传播是一种用于加快范围更新速度的优化技术。

查询函数是否也已更改？

C++ 代码

联系信息

关注我们

教程

面试题

在线编译器

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

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

线段树中的懒惰传播

简单的线段树更新函数是如何工作的？

C++ 代码

如果许多数组索引需要更新怎么办？

C++ 代码

懒惰传播是一种用于加快范围更新速度的优化技术。

查询函数是否也已更改？

C++ 代码

相关帖子

构建堆的时间复杂度

如何使用优先队列或堆实现栈

霍夫曼编码

距离之和

二叉树的直径

B 树性质

回文树

树-列表递归的伟大问题

将队列的前半部分与后半部分交错

归并排序和快速排序的区别

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器