线段树 - 给定范围的求和

2025年3月17日 | 阅读 7 分钟

让我们考虑以下问题来理解线段树。

我们有一个数组 arr[0... n-1]。我们应该能够：

查找索引 l 到 r 之间元素的和，其中 0 <= l <= r <= n-1
将数组中指定元素的值更改为新值 x。我们需要执行 arr[i] = x，其中 0 <= i <= n-1。

使用嵌套循环计算范围和

从 l 到 r 循环并计算给定范围内元素的和是一个直接的解决方案。只需输入 arr[i] = x 即可更改值。虽然第一个操作需要 O(n) 时间，但第二个操作只需要 O(1) 时间。

使用前缀和计算范围总和

另一种方法是创建一个新数组，并将从开头到 i 的总和存储在第 i 个索引处。现在更新操作需要 O(n) 时间，而给定范围的总和可以在 O(1) 时间内计算出来。如果查询操作很多而更新很少，这种方法效果很好。

使用线段树计算范围总和

最有效的方法是使用线段树；我们可以使用线段树在 O(log(N)) 时间内完成这两个操作。

线段树表示

输入数组中的元素是叶节点。
每个内部节点都以某种方式显示了叶节点的合并方式。对于某些问题，可能存在不同的合并方式。对于此问题，合并是指汇总一个节点下的叶节点。
线段树表示为树的数组表示。每个索引为 i 的节点的左子节点在索引 (2*i+1) 处，右子节点在索引 (2*i+2) 处，父节点在索引 (i - 1) / 2) 处。

从给定数组构建线段树

我们首先检查段 arr[0,... n-1]。每次我们将当前段分成两半（假设它还没有成为长度为 1 的段），对两半执行相同的操作，然后将每个此类段的结果存储在适当的节点中。

除了最后一层，创建的线段树的每一层都将完全填充。此外，由于我们总是将每个段在每一层分成两部分，因此该树将是一个完全二叉树。由于创建的树始终是一个具有 n 个叶子的完全二叉树，因此总会有 n-1 个内部节点。因此，总共有 2*n - 1 个节点。

给定数组的线段树有多高？

线段树的高度将为 log2N。由于树必须使用数组表示，并且必须保留父节点和子节点索引之间的关系，因此为线段树分配的内存量将为 (2 * 2log2n-1)。

搜索范围之和

线段树构建完成后如何计算和。计算元素和的算法如下：

int getSum(node, l, r) 
{
   if the range of the node is within l and r
        return value in the node
   else if the range of the node is completely outside l and r
        return 0
   else
    return getSum(node's left child, l, r) + 
           getSum(node's right child, l, r)
}

在上述实现中，我们需要解决三种情况。

遍历树时，如果当前节点的范围不属于指定范围，则该节点的值未添加到答案中。
如果给定范围与节点的范围部分重叠，则根据重叠情况向左或向右移动。
如果给定范围完全重叠，则将该范围添加到答案中。

更新值

更新可以像树构建和查询操作一样递归地执行。已向我们提供了过时的索引。令 diff 表示新值。从线段树的根开始，我们将 diff 添加到其范围内包含指定索引的每个节点。如果节点不包含指定索引在其范围内，我们不修改它。

C++ 代码

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

// C++ program to show segment tree operations like construction, query
// and update
#include <bits/stdc++.h>
using namespace std;

// A utility function to get the middle index from corner indexes.
int getMid(int s, int e) { return s + (e -s)/2; }

/* A recursive function to get the sum of values in the given range
	of the array. The following are parameters for this function.

	st --> Pointer to segment tree
	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., st[si]
	qs & qe --> Starting and ending indexes of query range */
int getSumUtil(int *st, int ss, int se, int qs, int qe, int si)
{
	// If segment of this node is a part of given range, then return
	// the sum of the segment
	if (qs <= ss && qe >= se)
		return st[si];

	// If segment of this node is outside the given range
	if (se < qs || ss > qe)
		return 0;

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

/* A recursive function to update the nodes which have the given
index in their range. The following are parameters
	st, si, ss and se are same as getSumUtil()
	i --> index of the element to be updated. This index is
			in the input array.
diff --> Value to be added to all nodes which have i in range */
void updateValueUtil(int *st, 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);
	}
}

// The function to update a value in input array and segment tree.
// It uses updateValueUtil() to update the value in segment tree
void updateValue(int arr[], int *st, int n, int i, int new_val)
{
	// Check for erroneous input index
	if (i < 0 || i > n-1)
	{
		cout<<"Invalid Input";
		return;
	}

	// Get the difference between new value and old value
	int diff = new_val - arr[i];

	// Update the value in array
	arr[i] = new_val;

	// Update the values of nodes in segment tree
	updateValueUtil(st, 0, n-1, i, diff, 0);
}

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

	return getSumUtil(st, 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
int constructSTUtil(int arr[], int ss, int se, int *st, int si)
{
	// If there is one element in array, store it in current node of
	// segment tree and return
	if (ss == se)
	{
		st[si] = arr[ss];
		return arr[ss];
	}

	// 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 = getMid(ss, se);
	st[si] = constructSTUtil(arr, ss, mid, st, si*2+1) +
			constructSTUtil(arr, mid+1, se, st, si*2+2);
	return st[si];
}

/* Function to construct segment tree from given array. This function
allocates memory for segment tree and calls constructSTUtil() to
fill the allocated memory */
int *constructST(int arr[], int n)
{
	// Allocate memory for the segment tree

	//Height of segment tree
	int x = (int)(ceil(log2(n)));

	//Maximum size of segment tree
	int max_size = 2*(int)pow(2, x) - 1;

	// Allocate memory
	int *st = new int[max_size];

	// Fill the allocated memory st
	constructSTUtil(arr, 0, n-1, st, 0);

	// Return the constructed segment tree
	return st;
}

// 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
	int *st = constructST(arr, n);

	// Print sum of values in array from index 1 to 3
	cout<<"Sum of values in given range = "<<getSum(st, n, 1, 3)<<endl;

	// Update: set arr[1] = 10 and update corresponding
	// segment tree nodes
	updateValue(arr, st, n, 1, 10);

	// Find sum after the value is updated
	cout<<"Updated sum of values in given range = "
			<<getSum(st, n, 1, 3)<<endl;
	return 0;
}

输出

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

时间复杂度： O(N*log(N))
辅助空间：O(N)

下一主题2-3 树（搜索、插入和删除）

线段树 - 给定范围的求和

使用嵌套循环计算范围和

使用前缀和计算范围总和

使用线段树计算范围总和

线段树表示

从给定数组构建线段树

给定数组的线段树有多高？

搜索范围之和

更新值

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++ 代码

相关帖子

最多进行两次股票买卖的最大利润

中国邮递员或路线检查问题

递归移除所有相邻重复项

根到叶子节点路径上不同节点的数量最多

数据结构中的线性搜索和二分搜索是什么

设计一个支持常数时间插入、删除、搜索和 getRandom 的数据结构

C++ 中按第一个和第二个元素排序的对优先队列

打印数字的第 k 个最低有效位

设计和实现特殊栈数据结构

查找二叉树中两个节点的直接父节点

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器