北京专业网站翻译影音字幕翻译速记速记快而高效,中山免费网站建设,东阳建设公司网站,网站开发模块目录 1.概述2.代码实现2.1.聚合操作——求和2.2.聚合操作——求和、求最小值、求最大值 3.应用4.与前缀和之间的区别 更多数据结构与算法的相关知识可以查看数据结构与算法这一专栏。 1.概述
#xff08;1#xff09;线段树 (Segment Tree) 是一种二叉树形数据结构#xff… 目录 1.概述2.代码实现2.1.聚合操作——求和2.2.聚合操作——求和、求最小值、求最大值 3.应用4.与前缀和之间的区别 更多数据结构与算法的相关知识可以查看数据结构与算法这一专栏。 1.概述
1线段树 (Segment Tree) 是一种二叉树形数据结构经常用于高效地处理一维区间的各种查询和修改问题。
2一个线段树通常对应于一个区间每个节点表示一个区间具体如下图所示。
对于线段树中的每个节点它有一个区间范围和一个值。叶节点表示区间中的单个元素而非叶子节点表示区间中的所有元素。线段树的每个节点表示区间的一部分其左子树表示左半部分区间右子树表示右半部分区间。因此线段树的叶节点数总是等于数据元素的个数而线段树的高度为 ⌈logn⌉ 1其中 n 为元素总个数。 ① 上图来自线段树_百度百科。 ② 一般来说在代码中会用数组来存储某个区间内的元素该数组内的元素可以是无序或者有序的例如nums [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 或者 nums [2, 4, -1, 0, 9] 等。上图中线段树中的区间正好是前一个数组。 3线段树的主要优势是能够在 O(logn) 时间复杂度内执行区间查询如最大值、最小值、区间和等和区间修改操作如区间加、区间减等因此它非常适合解决那些需要频繁区间查询和修改的问题。
2.代码实现
1在线段树中区间的聚合值是指该区间内元素的某种聚合操作的结果。这个聚合操作可以是求和、求最小值、求最大值等。聚合值的具体含义取决于所解决的问题本节中分别给出以下两种情况。
2线段树的构建过程与 108.将有序数组转换为二叉搜索树这题类似具体如下
定义线段树节点线段树是一种二叉树每个节点代表一个区间。每个节点包含了该区间的起始点start、结束点end以及其他你可能需要的附加信息。定义递归构建函数创建一个递归函数来构建线段树。该函数接收输入参数为当前节点、当前区间的起始点和结束点。基本情况处理对于当前节点如果起始点和结束点相等表示当前节点为叶子节点直接返回。划分区间计算当前区间的中点 mid将区间分割成两个子区间。通常是将区间一分为二可以选择将 mid 设置为 (startend)/2。递归构建左子树和右子树调用递归函数传入左子树和右子树的起始点和中点以构建左右子树。合并信息在递归回溯时将左右子树的信息合并到当前节点。这通常取决于你的问题需求可以是求和、求最大值、求最小值等。返回根节点递归构建完成后返回根节点。
2.1.聚合操作——求和
1实现区间求和操作包括修改区间的某个元素的代码实现如下
class SegmentTree {//线段树数组segmentTree[i] 表示线段树的第 i 个节点(区间)的聚合值本代码中是区间和int[] segmentTree;//原始数组int[] nums;public SegmentTree(int[] nums) {this.nums nums;int n nums.length;//确定树的高度int height (int) (Math.ceil(Math.log(n) / Math.log(2))) 1;//根据树的高度计算需要的线段树数组大小int maxSize (int) Math.pow(2, height) - 1;//创建线段树数组segmentTree new int[maxSize];//构建线段树buildTree(0, 0, n - 1);}//构建线段树private int buildTree(int index, int start, int end) {//叶子节点if (start end) {//叶子节点存储对应的原始数组值segmentTree[index] nums[start];return segmentTree[index];}int mid start (end - start) / 2; // 计算中间位置//分别递归构建左子树和右子树segmentTree[index] buildTree(2 * index 1, start, mid) buildTree(2 * index 2, mid 1, end);return segmentTree[index];}//更新原始数组中的某个元素并同时更新线段树public void update(int i, int val) {//计算变化的差值int diff val - nums[i];//更新原始数组中的值nums[i] val;//更新线段树updateTree(0, 0, nums.length - 1, i, diff);}//更新线段树private void updateTree(int index, int start, int end, int i, int diff) {if (i start || i end) {//该节点不包含要更新的元素直接返回return;}//更新当前节点的值segmentTree[index] diff;if (start ! end) {//计算中间位置int mid start (end - start) / 2;//递归更新左子树updateTree(2 * index 1, start, mid, i, diff);//递归更新右子树updateTree(2 * index 2, mid 1, end, i, diff);}}//查询线段树中某个区间的和public int querySum(int left, int right) {return queryTree(0, 0, nums.length - 1, left, right);}// 查询线段树private int queryTree(int index, int start, int end, int left, int right) {if (left end || right start) {//区间不相交返回 0return 0;}if (left start right end) {//当前节点表示的区间完全被查询区间包含直接返回当前节点的值return segmentTree[index];}//计算中间位置int mid start (end - start) / 2;//分别递归查询左子树和右子树return queryTree(2 * index 1, start, mid, left, right) queryTree(2 * index 2, mid 1, end, left, right);}
}2测试代码如下
class SegmentTreeTest {public static void main(String[] args) {//原始数组可以是有序或者无序的int[] nums {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};SegmentTree segmentTree new SegmentTree(nums);//查询区间 [1, 4] 的和即 nums[1...4] 的和int sum segmentTree.querySum(1, 4);System.out.println(Sum of range [1, 4]: sum);//将数组下标为 2 的元素更新为 6即更新 nums[2] 6同时更新线段树segmentTree.update(2, 6);//再次查询区间 [1, 4] 的和sum segmentTree.querySum(1, 4);System.out.println(Updated sum of range [1, 4]: sum);}
}输出结果如下
Sum of range [1, 4]: 14
Updated sum of range [1, 4]: 172.2.聚合操作——求和、求最小值、求最大值
1实现区间求和、求最小值、求最大值操作包括修改区间的某个元素的代码实现如下
class SegmentTree {private Node root;//定义节点类用于表示某个区间private class Node {int start;int end;int sum;int max;int min;Node left;Node right;Node(int start, int end) {this.start start;this.end end;this.sum 0;this.max Integer.MIN_VALUE;this.min Integer.MAX_VALUE;}}public SegmentTree(int[] nums) {this.root build(nums, 0, nums.length - 1);}//构建线段树private Node build(int[] nums, int start, int end) {if (start end) {return null;}Node node new Node(start, end);if (start end) {node.sum nums[start];node.max nums[start];node.min nums[start];} else {int mid start (end - start) / 2;node.left build(nums, start, mid);node.right build(nums, mid 1, end);node.sum node.left.sum node.right.sum;node.max Math.max(node.left.max, node.right.max);node.min Math.min(node.left.min, node.right.min);}return node;}//查询线段树中某个区间的和public int queryRangeSum(int start, int end) {return queryRangeSum(root, start, end);}private int queryRangeSum(Node node, int start, int end) {if (node.start start node.end end) {return node.sum;}int mid node.start (node.end - node.start) / 2;if (end mid) {return queryRangeSum(node.left, start, end);} else if (start mid) {return queryRangeSum(node.right, start, end);} else {return queryRangeSum(node.left, start, mid) queryRangeSum(node.right, mid 1, end);}}//查询线段树中某个区间的最大值public int queryRangeMax(int start, int end) {return queryRangeMax(root, start, end);}private int queryRangeMax(Node node, int start, int end) {if (node.start start node.end end) {return node.max;}int mid node.start (node.end - node.start) / 2;if (end mid) {return queryRangeMax(node.left, start, end);} else if (start mid) {return queryRangeMax(node.right, start, end);} else {return Math.max(queryRangeMax(node.left, start, mid),queryRangeMax(node.right, mid 1, end));}}//查询线段树中某个区间的最小值public int queryRangeMin(int start, int end) {return queryRangeMin(root, start, end);}private int queryRangeMin(Node node, int start, int end) {if (node.start start node.end end) {return node.min;}int mid node.start (node.end - node.start) / 2;if (end mid) {return queryRangeMin(node.left, start, end);} else if (start mid) {return queryRangeMin(node.right, start, end);} else {return Math.min(queryRangeMin(node.left, start, mid),queryRangeMin(node.right, mid 1, end));}}//更新原始数组中的某个元素并同时更新线段树public void update(int index, int value) {update(root, index, value);}private void update(Node node, int index, int value) {if (node.start node.end) {node.sum value;node.max value;node.min value;return;}int mid node.start (node.end - node.start) / 2;if (index mid) {update(node.left, index, value);} else {update(node.right, index, value);}node.sum node.left.sum node.right.sum;node.max Math.max(node.left.max, node.right.max);node.min Math.min(node.left.min, node.right.min);}
}2测试代码如下
class SegmentTreeTest {public static void main(String[] args) {//原始数组可以是有序或者无序的int[] nums {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};SegmentTree segmentTree new SegmentTree(nums);//查询区间 [1, 4] 的和即 nums[1...4] 的和int sum segmentTree.queryRangeSum(1, 4);System.out.println(Sum of range [1, 4]: sum);int max segmentTree.queryRangeMax(1, 4);System.out.println(Max of range [1, 4]: max);int min segmentTree.queryRangeMin(1, 4);System.out.println(Min of range [1, 4]: min);//将数组下标为 1 的元素更新为 0即更新 nums[1] 0同时更新线段树segmentTree.update(1, 0);//将数组下标为 2 的元素更新为 6即更新 nums[2] 6同时更新线段树segmentTree.update(2, 6);//再次查询区间 [1, 4] 的和sum segmentTree.queryRangeSum(1, 4);System.out.println(Updated sum of range [1, 4]: sum);max segmentTree.queryRangeMax(1, 4);System.out.println(Updated Sum of range [1, 4]: max);min segmentTree.queryRangeMin(1, 4);System.out.println(Updated Min of range [1, 4]: min);}
}输出结果如下
Sum of range [1, 4]: 14
Max of range [1, 4]: 5
Min of range [1, 4]: 2
Updated sum of range [1, 4]: 15
Updated Sum of range [1, 4]: 6
Updated Min of range [1, 4]: 03.应用
1LeetCode 中的 307.区域和检索 - 数组可修改这题便是对线段树的具体应用其题目如下。显然使用上面的代码可以直接求解。 2大家可以去 LeetCode 上找相关的线段树的题目来练习或者也可以直接查看 LeetCode 算法刷题目录 (Java) 这篇文章中的线段树章节。如果大家发现文章中的错误之处可在评论区中指出。
4.与前缀和之间的区别
1线段树和前缀和是两种常见的用于解决区间查询问题的数据结构它们有一些区别
数据结构 线段树是一种二叉树结构用于处理区间查询和更新操作。它将区间划分为不相交的子区间并将每个子区间的信息存储在相应节点中。前缀和是一个数组用于存储前缀和值。它通过计算数组元素累加和的方式存储数据。 功能 线段树可以支持多种区间查询操作例如区间和、区间最大值、区间最小值等。它可以在 O(logN) 的时间复杂度内完成查询和更新操作。前缀和主要用于计算数组中特定区间的和。它可以在 O(1) 的时间内计算出给定区间的和但只能处理区间和的查询。 空间复杂度 线段树的空间复杂度为 O(N)其中 N 是数组的大小。它需要存储整个线段树的节点。前缀和的空间复杂度为 O(N)其中 N 是数组的大小。它只需要存储一个与数组大小相等的前缀和数组。 应用场景 线段树通常用于解决需要频繁进行区间查询和更新操作的问题比如计算数组的区间和、区间最大值和最小值等。前缀和通常用于解决需要频繁计算数组特定区间和的问题比如计算子数组的和、快速判断数组中是否存在某个区间的和等。
2综上所述线段树和前缀和在功能和应用场景上略有不同选择使用哪种数据结构取决于具体的问题需求和效率要求。 有关前缀和的相关知识可以参考【数据结构】前缀和数组这篇文章。
