数据结构-线段树

谁践踏了优雅 2023-02-14 05:51 118阅读 0赞

# 数据结构-线段树 #

# 转载声明 #

***本文大量内容系转载自以下文章，有删改，并参考其他文档资料加入了一些内容：***

*  [leetcode-线段树][leetcode-]  
    作者： leetcode
 *  [【数据结构】线段树（Segment Tree）][Segment Tree]  
    作者： 正月点灯笼

# 1 概述 #

线段树是一种非常灵活的数据结构，它可以用于解决多种范围查询问题，比如`在对数时间logN内从数组中找到最小值、最大值、总和、最大公约数、最小公倍数等`。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70]![在这里插入图片描述][20200601114004711.png]  
在上图所给出的示例中，每个叶节点都包含初始的数组元素 \{1,3,5,7,9,11\}。内部节点包含范围内相应元素的总和 ：

*  (9) 是从索引 0 到索引 2 的元素之和（1 + 3 + 5 = 9）
 *  根节点 (35) 是它的两个子节点 (6) 和 (29) 的和，也是整个数组的和。

线段树可以分为以下三个步骤：

1.  从给定数组构建线段树的预处理步骤。
2.  修改元素时更新线段树。
3.  使用线段树进行区域和检索。

# 2 构建线段树 #

## 2.1 概述 ##

![在这里插入图片描述][20200601105312440.png]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 1]

public SegmentedTree1(int[] nums) { 
        this.nums = nums;
        tree = new int[4 * nums.length];
        buildSegmentedTree(0, 0, nums.length - 1);
    }
    
    /** * 构建线段树 * @param nodeIndex 当前访问的线段树数组下标 * @param start 该节点区间起点 * @param end 该节点区间终点 */
    public void buildSegmentedTree(int nodeIndex, int start, int end){ 
        if(start == end){ 
            tree[nodeIndex] = nums[start];
            return;
        }
        // 求左右子树节点索引下标
        int leftNode = 2 * nodeIndex + 1;
        int rightNode = 2 * nodeIndex + 2;
        int mid = (start + end) / 2;
        // 左右子树构建线段树
        buildSegmentedTree(leftNode, start, mid);
        buildSegmentedTree(rightNode, mid + 1, end);
        // 计算当前节点表示的区间和
        tree[nodeIndex] = tree[leftNode] + tree[rightNode];
    }

int[] tree;
    int n;
    public NumArray(int[] nums) { 
        if (nums.length > 0) { 
            n = nums.length;
            tree = new int[n * 2];
            buildTree(nums);
        }
    }
    private void buildTree(int[] nums) { 
        for (int i = n, j = 0;  i < 2 * n; i++,  j++)
            tree[i] = nums[j];
        for (int i = n - 1; i > 0; --i)
            tree[i] = tree[i * 2] + tree[i * 2 + 1];
    }

## 2.2 复杂度分析 ##

### 2.2.1 时间复杂度：O(n)。 ###

因为我们在 for 循环的每次迭代中计算一个节点的和，而一个线段树中大约有 2n个节点。

这可以通过以下方式证明：具有 n 个元素的数组线段树有 n 个叶节点（数组元素本身），每一层中的节点数是下面一层中节点数的一半。

因此，如果我们按层对节点数求和，我们将得到：  
`n+n/2+n/4+n/8+…+1≈2n`

### 2.2.2 空间复杂度：O(n) ###

我们用了 2n 的额外空间来存储整个线段树。

# 3 更新线段树 #

## 3.1 概述 ##

当我们更新数组中某个索引 i 处的元素时，我们需要重建线段树，因为一些树节点上的和值也会随之产生变化。我们将再次使用自下而上的方法。

首先更新存储 tree\[i\] 元素的叶节点。从那里我们将一路向上，直到根节点，并用其子节点值的总和来更新每个父节点的值。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 2]  
比如上图，我们要更新arr\[4\] = 6，那么就从原arr\[4\]=9的叶节点开始，自底向上更新和，直到根节点。

/** * 修改指定数组下标元素的值 * @param i 原始数组下标 * @param val 要修改的值 */
    public void update(int i, int val) { 
        update(0, 0, nums.length - 1, i, val);
    }
    
    
    /** * 修改指定数组下标元素的值，并自底向上修改影响到的线段树节点 * @param nodeIndex 当前访问的线段树数组下标 * @param start 该节点区间起点 * @param end 该节点区间终点 * @param i 原始数组下标 * @param val 要修改的值 */
    private void update(int nodeIndex, int start, int end, int i, int val) { 
        if(start == end){ 
            tree[nodeIndex] = val;
            nums[i] = val;
        } else{ 
            // 根据要改的数组下标i和区间中点进行对比，确定要改哪个子树
            int mid = (start + end) / 2;
            int leftNode = nodeIndex * 2 + 1;
            int rightNode = nodeIndex * 2 + 2;
            if(i <= mid){ 
                update(leftNode, start, mid, i, val);
            }else{ 
                update(rightNode, mid + 1, end, i, val);
            }
            // 改完子树后更新当前节点表示的区间和
            tree[nodeIndex] = tree[leftNode] + tree[rightNode];
        }
    }

void update(int pos, int val) { 
    	// n 为原始数组长度
    	// pos为i元素对应的叶节点索引
        pos += n;
        tree[pos] = val;
        while (pos > 0) { 
            int left = pos;
            int right = pos;
            if (pos % 2 == 0) { 
                right = pos + 1;
            } else { 
                left = pos - 1;
            }
            // parent is updated after child is updated
            tree[pos / 2] = tree[left] + tree[right];
            pos /= 2;
        }
    }

## 3.2 复杂度分析 ##

### 3.2.1时间复杂度：O(logn)。 ###

算法的时间复杂度为 O(logn)，因为有几个树节点的范围包括第 i 个数组元素，每个层上都有一个。共有log(n) 层。

### 3.2.2 空间复杂度：O(1) ###

# 4 区域和检索 #

## 4.1 概述 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 3]  
比如计算区间\[2,5\]的和。则从根节点开始分为两个区间分别搜索：

*  左边搜索\[2\]，需要搜索到叶节点
 *  右边搜索\[3-5\]，一次就搜到了

所以计算区间和的时间复杂度为log(N)  
![在这里插入图片描述][20200601110619682.png]

public int sumRange(int i, int j) { 
        // 合法性验证
        if(i < 0 || i > j || j >= nums.length){ 
            return 0;
        }
    
        return sumRange(0, 0, nums.length - 1, i, j);
    }
    
    private int sumRange(int nodeIndex, int start, int end, int i, int j) { 
        if(start == end || (i == start && j == end)){ 
            return tree[nodeIndex];
        }else{ 
            int mid = (start + end) / 2;
            int leftNode = nodeIndex * 2 + 1;
            int rightNode = nodeIndex * 2 + 2;
            if(i > mid){ 
                return sumRange(rightNode, mid + 1, end, i, j);
            } else if(j <= mid){ 
                return sumRange(leftNode, start, mid, i, j);
            }else{ 
                return sumRange(leftNode, start, mid, i, mid) + sumRange(rightNode, mid + 1, end, mid + 1, j);
            }
        }
    }

public int sumRange(int l, int r) { 
        // get leaf with value 'l'
        l += n;
        // get leaf with value 'r'
        r += n;
        int sum = 0;
        while (l <= r) { 
            if ((l % 2) == 1) { 
               sum += tree[l];
               l++;
            }
            if ((r % 2) == 0) { 
               sum += tree[r];
               r--;
            }
            l /= 2;
            r /= 2;
        }
        return sum;
    }

## 4.2 复杂度分析 ##

### 4.2.1 时间复杂度：O(logn) ###

因为在算法的每次迭代中，我们会向上移动一层，要么移动到当前节点的父节点，要么移动到父节点的左侧或者右侧的兄弟节点，直到两个边界相交为止。在最坏的情况下，这种情况会在算法进行logn 次迭代后发生在根节点。

### 4.2.2 空间复杂度：O(1) ###

[leetcode-]: https://leetcode-cn.com/problems/range-sum-query-mutable/solution/qu-yu-he-jian-suo-shu-zu-ke-xiu-gai-by-leetcode/
[Segment Tree]: https://www.bilibili.com/video/av47331849/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200601114131215.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA==,size_16,color_FFFFFF,t_70
[20200601114004711.png]: https://img-blog.csdnimg.cn/20200601114004711.png
[20200601105312440.png]: https://img-blog.csdnimg.cn/20200601105312440.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200601115226286.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/2020060111502832.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200601114603908.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA==,size_16,color_FFFFFF,t_70
[20200601110619682.png]: https://img-blog.csdnimg.cn/20200601110619682.png