详解线段树 ---更新查询

以你之姓@ 2024-03-25 15:47 75阅读 0赞

**目录**

一.问题引入

二.线段树

1.什么是线段树

2.线段树的举例

三.构建线段树

1.思路分析

2.代码实现

四.更新

1.思路分析

2.代码实现

五.查询

1.思路分析

2.代码实现

--------------------

## 一.问题引入 ##

有n个整数的数组,我们要 求解下标从left到right的元素之和为多少(query操作),然后还需要更新下标为index的值改为val(update操作),这个时候的时间复杂度为多少.

**方法一:**对于第一个问题(query)直接相加,这样的时间复杂度为O(n),第二个问题(update)的时间复杂度为O(1)

**方法二:**如果我们需要多次的query操作,我们是否有方法可以将降低时间复杂度?这个时候最好的办法就是把这n个整数的前缀和数组求解出来,每一次只需要**prefix\[right\]-prefix\[left-1\]**即可求解出来答案,这样的时间复杂度就降到了O(1),但是这个时候update操作的时间复杂度就升到了O(n),因为我们需要对前缀和数组index之后都进行修改.具体可以参考这篇博客看前缀和相关的内容:[Java之前缀和算法\_java前缀和算法\_允歆辰丶的博客-CSDN博客][Java_java_-CSDN]

因此当我们采用无论哪一种方法,对于一种操作的时间复杂度可能很低,但是对另外一种操作的时间复杂度是很高的,因此是否可以有一种方法,可能将两种操作的时间复杂度平均一下,当然有,就是我们接下来要介绍的线段树,对于两种操作的时间复杂度都为O(log n);

## 二.线段树 ##

### 1.什么是线段树 ###

线段树是一种经典的数据结构，用于处理区间查询问题，例如**区间求和**、**区间最小值**、**区间最大值**等。它的基本思想是将区间**递归地划分为若干个子区间**，并将每个子区间的信息保存在一个节点中，从而形成一棵树形结构，即线段树。

线段树的每个**节点**都代表**一个区间**，如果该节点表示的区间与待查询的区间有**交集**，那么该节点保存的信息就可能对查询有用。因此，在查询时，只需要**访问与待查询区间相交的节点**即可，而不需要访问整棵树。

线段树通常使用数组来实现，其空间复杂度为 O(n)，其中n是区间的长度。线段树的建树复杂度为 O(n)，单次查询复杂度为 O(\\log n)。

### 2.线段树的举例 ###

我们对数组arr(如下图)构建一颗线段树(如下下图),此时叶子结点就是数组下标为index的值,他们的根结点为叶子结点的之和,一层层向上,根结点为整个数组的和36(也就是index为0到5的和)

![c5c5b109e8894bb58c5bc355e0f6681f.png][]

![48ffa3a8e4f34484bb19081ec37e4b14.png][]

## 三.构建线段树 ##

### 1.思路分析 ###

构建一颗线段树可以用数组来模拟树的实现,知道根结点下标(也就是tree数组的node),这个时候它的左子节点为:node\_left = node \* 2 + 1;右子节点为:node\_right = node \* 2 + 2;node左节点的对应arr数组的下标范围为\[start,mid\],node右节点的对应arr数组的下标范围为\[mid,end\],这个时候我们进行递归创建这个tree数组,我们可以知道递归要到叶子结点,对叶子结点的下标进行赋值,然后再一步步回溯向上对上一层的父节点进行赋值,最后完成对根结点的赋值,所以我们递归的出口为递归到叶子结点,也就是start==end,这个时候赋值 tree\[node\] = arr\[start\];

### 2.代码实现 ###

public static void buildTree(int[] arr, int[] tree, int node, int start, int end) {
            if (start == end) {
                tree[node] = arr[start];
                return;
            }
            int mid = (start + end) / 2;
            int node_left = node * 2 + 1;
            int node_right = node * 2 + 2;
            buildTree(arr, tree, node_left, start, mid);
            buildTree(arr, tree, node_right, mid + 1, end);
            tree[node] = tree[node_left] + tree[node_right];
    
        }

## 四.更新 ##

### 1.思路分析 ###

当我们需要对arr数组中的下标为index的元素进行数值的修改,这个时候也需要对线段树进行更新,例如将下标为3的数值修改为6,这个时候需要递归到下标范围为3的tree数组的下标,然后对值进行修改,然后一层层向上回溯对这半区的树值全部进行修改,我们只需要加上一个范围的判断,选择往左子树递归还是向右子树递归即可

![d4c39f47174b4938a05e5e5e2bd78f86.png][]

### 2.代码实现 ###

public static void updateTree(int[] arr, int[] tree, int node, int start, int end, int index, int val) {
            if (start == end) {
                arr[index] = val;
                tree[node] = val;
                return;
            }
            int mid = (start + end) / 2;
            int node_left = node * 2 + 1;
            int node_right = node * 2 + 2;
    
            if (index >= start && index <= mid) {
                updateTree(arr, tree, node * 2 + 1, start, mid, index, val);
            } else {
                updateTree(arr, tree, node * 2 + 2, mid + 1, end, index, val);
            }
            tree[node] = tree[node_left] + tree[node_right];
    
    
        }

## 五.查询 ##

### 1.思路分析 ###

查询代码实现起来是有一定的复杂,首先我们可以先判断返回值为0的情况,也就是需要求和的范围不在当前树的根结点所在的范围内的,一共有两种情况:一种当start>right,一种当left>end,这个时候直接返回0.

![ba9021d4b9af4d4c975fe88ee904477c.png][]![2a51d1145d40486fbb137d0a42c4e30b.png][]

还有当出现如下图的情况时,直接返回当前结点的值,没必要继续向下递归,因为此时范围全部都符合了

![afe91779588f4cf7946c0bb5f7ef41eb.png][]

这个时候最后我们需要把左边的符合范围的和 加上 右边符合范围的和 ,最终的结果就是我们需要求解的范围.

### 2.代码实现 ###

/**
         * 
         * @param arr  原数组
         * @param tree  构建的tree数组
         * @param node  根结点在tree数组的下标
         * @param start 原数组从start索引开始
         * @param end   原数组到end索引结束
         * @param left  求和从left索引开始
         * @param right  到right索引结束的和
         * @return
         */
        public static int queryTree(int[] arr, int[] tree, int node, int start, int end, int left, int right) {
            if (right < start || end < left) {
                return 0;
            } else if (left <= start && right >= end) {
                return tree[node];
            }
            int mid = (start + end) / 2;
            int node_left = node * 2 + 1;
            int node_right = node * 2 + 2;
            int sum_left = queryTree(arr, tree, node_left, start, mid, left, right);
            int sum_right = queryTree(arr, tree, node_right, mid + 1, end, left, right);
    
            return sum_left + sum_right;
    
    
        }

[Java_java_-CSDN]: https://blog.csdn.net/qq_64580912/article/details/129150575?spm=1001.2014.3001.5501
[c5c5b109e8894bb58c5bc355e0f6681f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/5a3844679f5e48fb8e9c704bb31b1417.png
[48ffa3a8e4f34484bb19081ec37e4b14.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/70afd6a5bccb45f3b9131e02830755fa.png
[d4c39f47174b4938a05e5e5e2bd78f86.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/0c90f7d65fb14e8d838de57321617c7d.png
[ba9021d4b9af4d4c975fe88ee904477c.png]: https://img-blog.csdnimg.cn/ba9021d4b9af4d4c975fe88ee904477c.png
[2a51d1145d40486fbb137d0a42c4e30b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/d92af9277fe243b586bde488cc81cd58.png
[afe91779588f4cf7946c0bb5f7ef41eb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/0ca388187a2b4d4db39253c7ffc4c0ac.png