数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究线段树 | 给定范围的和
线段树
线段树是一种用于存储区间和线段的树形数据结构。它是一种静态结构，即一旦构建完成就无法修改。线段树用于处理数组或类似线性数据结构上的范围查询。
在线段树中，我们将输入数组划分为多个线段，并预先计算这些线段的值。线段树中的每个节点都表示数组的一个区间或线段。根节点表示整个数组，每个子节点表示通过划分父节点形成的线段。这种划分导致叶子节点表示数组的单个元素。
用于范围求和查询的线段树 -
Original Array: [7, 1, 2, 3, 6, 5, 0, 4]
Segment Tree:
38
/ \
13 25
/ \ / \
8 5 11 4
/ \ / \ / \ / \
7 1 2 3 6 5 0 4
线段树对于每个范围查询和更新操作的复杂度为 O(logN)。
范围求和查询 - RSQ 是一个常见问题，对于给定的数组，我们需要找到指定范围内所有元素的总和。线段树是解决此问题最有效的数据结构。
问题陈述
给定一个包含 N 个元素的整数数组 arr[] 以及起始和结束索引。任务是找到范围 [start, end] 内所有元素的总和。
示例 1
输入
N = 8
arr[] = {1, 7, 8, 9, 5, 2, 3, 4}
start = 2
end = 6
输出
27
解释
Array within the specified range is: {8, 9, 5, 2, 3}
In the given range, the sum of elements = 8 + 9 + 5 + 2 + 3 = 27.
示例 2
输入
N = 3
arr[] = {1, 3, 2}
start = 1
end = 1
输出
3
解释
Array within the specified range is: {3}
In the given range, the sum of elements = 3.
解决方案方法
范围求和查询问题可以通过以下步骤解决 -
为输入数组构建线段树。
递归查找树中包含在查询中的线段。每个线段可以归类为以下之一 -
完全重叠 - 当前线段完全在查询范围内。
无重叠 - 当前线段完全在查询范围之外。
部分重叠 - 当前线段部分覆盖查询范围。
构建线段树的伪代码
function segmentTreeUtil(arr, seg_start, seg_end, tree, curr):
if seg_start == seg_end:
tree[curr] = arr[seg_start]
return arr[seg_start]
mid = getMid(seg_start, seg_end)
tree[curr] = segmentTreeUtil(arr, seg_start, mid, tree, curr * 2 + 1) + segmentTreeUtil(arr, mid + 1, seg_end, tree, curr * 2 + 2)
return tree[curr]
function segmentTree(arr, n):
x = ceil(log2(n))
max_size = 2 * pow(2, x) - 1
tree = new int[max_size]
segmentTreeUtil(arr, 0, n - 1, tree, 0)
return tree
RSQ 的伪代码
function RSQUtil(tree, seg_start, seg_end, start, end, curr):
if start <= seg_start AND end >= seg_end:
return tree[curr]
if seg_end < start OR seg_start > end:
return 0
mid = getMid(seg_start, seg_end)
return RSQUtil(tree, seg_start, mid, start, end, 2 * curr + 1) + RSQUtil(tree, mid + 1, seg_end, start, end, 2 * curr + 2)
function RSQ(tree, n, start, end):
if start < 0 OR end > n - 1 OR start > end:
print "Query Range Invalid"
return -1
return RSQUtil(tree, 0, n - 1, start, end, 0)
示例：C++ 实现
以下代码构建了一个线段树来解决 RSQ 问题。
#include <bits/stdc++.h>
using namespace std;
int getMid(int x, int y){
return x + (y - x) / 2;
}
// Recursive function used to find the sum of elements in the query range
int RSQUtil(int *tree, int seg_start, int seg_end, int start, int end, int curr){
// Complete Overlap
if (start <= seg_start && end >= seg_end)
return tree[curr];
// No Overlap
if (seg_end < start || seg_start > end)
return 0;
// Partial Overlap
int mid = getMid(seg_start, seg_end);
return RSQUtil(tree, seg_start, mid, start, end, 2 * curr + 1) + RSQUtil(tree, mid + 1, seg_end, start, end, 2 * curr + 2);
}
// Calculates RSQ by calling RSQUtil(
int RSQ(int *tree, int n, int start, int end){
if (start < 0 || end > n - 1 || start > end){
cout << "Query Range Invalid";
return -1;
}
return RSQUtil(tree, 0, n - 1, start, end, 0);
}
// Creates Segment Tree for input array
int segmentTreeUtil(int arr[], int seg_start, int seg_end, int *tree, int curr){
// Base Case of only one element in array
if (seg_start == seg_end){
tree[curr] = arr[seg_start];
return arr[seg_start];
}
// Dividing array into segments
int mid = getMid(seg_start, seg_end);
tree[curr] = segmentTreeUtil(arr, seg_start, mid, tree, curr * 2 + 1) + segmentTreeUtil(arr, mid + 1, seg_end, tree, curr * 2 + 2);
return tree[curr];
}
// Creates Segment Tree by allocating memmory and calling segmentTreeUtil(
int *segmentTree(int arr[], int n){
int x = (int)(ceil(log2(n)));
int max_size = 2 * (int)pow(2, x) - 1;
int *tree = new int[max_size];
segmentTreeUtil(arr, 0, n - 1, tree, 0);
return tree;
}
int main(){
int arr[] = {1, 7, 8, 9, 5, 2, 3, 4};
int n = 8;
int *tree = segmentTree(arr, n);
int start = 2;
int end = 6;
cout << "Sum = " << RSQ(tree, n, start, end) << endl;
return 0;
}
输出
Sum = 27
时间复杂度 - 构建树的时间复杂度为 O(N)，每个 RSQ 的时间复杂度为 O(logn)。因此，对于 Q 个查询，时间复杂度为 O(Q*logN)。
空间复杂度 - O(N)
结论
总之，使用线段树的范围求和查询 (RSQ) 是一种有效的数据结构和算法，用于查找数组给定范围内的最小元素。每个查询的时间复杂度为 O(logN)，这优于具有 O(N) 复杂度的朴素迭代数组方法。
更新于: 2023-11-03
569 次查看
广告