资讯专栏INFORMATION COLUMN

我理解的数据结构(八)—— 线段树(SegmentTree)

waltr / 1726人阅读

摘要:示例解题代码注意,如果要在上提交解答,必须把接口和类的代码一并提交,这里并没有在写类中

我理解的数据结构(八)—— 线段树(SegmentTree) 一、什么是线段树

1.最经典的线段树问题:区间染色
有一面墙,长度为n,每次选择一段墙进行染色,m次操作后,我们可以看见多少种颜色?m次操作后,我们可以在[i, j]区间内看见多少种颜色?

数据结构 染色操作 查询操作
数组 O(n) O(n)

2.其他应用场景
2017年注册用户中消费最高的用户?消费最少的用户?学习时间最长的用户?

3.复杂度比较

数据结构 更新 查询
数组 O(n) O(n)
线段树 O(logn) O(logn)

4.线段树原理图
以求和为例:

二、线段树基础

1.基础

线段树不是完全二叉树

线段树是平衡二叉树(整棵树最大深度和最小深度最大差为1)

线段树依然可以用数组表示

把不存在的节点看成null,线段树即是完全二叉树

2.数组存储线段树的空间需求

0层 1层 ... h-1层
1 2 ... 2^(h-1)

对满二叉树:

h层,一共有2^h-1个节点(大约2^h)

最后一层(h-1)层,有2^(h-1)个节点

最后一层的节点数大致等于前面所有层节点之和

如果需要存储n个元素

n=2^k,只需要2n的空间

n=2^k+1,需要4n的空间

三、线段树基础代码

</>复制代码

  1. public class SegmentTree {
  2. private E[] data;
  3. private E[] tree;
  4. public SegmentTree(E[] arr) {
  5. data = (E[])new Object[arr.length];
  6. for (int i = 0; i < arr.length; i++) {
  7. data[i] = arr[i];
  8. }
  9. tree = (E[])new Object[4 * arr.length];
  10. }
  11. // 获取元素个数
  12. public int getSize() {
  13. return data.length;
  14. }
  15. // 获取某个索引上的值
  16. private E get(int index) {
  17. if (index < 0 || index >= data.length) {
  18. throw new IllegalArgumentException("index is illegal");
  19. }
  20. return data[index];
  21. }
  22. // 返回完全二叉树的数组表示中,一个索引所表示的元素的左子树的索引
  23. private int leftChild(int index) {
  24. return 2 * index + 1;
  25. }
  26. // 返回完全二叉树的数组表示中,一个索引所表示的元素的右子树的索引
  27. private int rightChild(int index) {
  28. return 2 * index + 2;
  29. }
  30. }
四、创建线段树代码

1.定义融合器接口

</>复制代码

  1. public interface Merge {
  2. // 区间的元素如何定义由用户决定
  3. E merge(E a, E b);
  4. }

2.创建线段树代码

</>复制代码

  1. private Merge merge;
  2. public SegmentTree(E[] arr, Merge merge) {
  3. // 线段树的融合器,用于定义线段树的区间元素到底如何存储
  4. this.merge = merge;
  5. data = (E[])new Object[arr.length];
  6. for (int i = 0; i < arr.length; i++) {
  7. data[i] = arr[i];
  8. }
  9. tree = (E[])new Object[4 * arr.length];
  10. buildSegmentTree(0, 0, data.length - 1);
  11. }
  12. // 递归:在treeIndex的位置创建表示区间[l,r]的线段树
  13. private void buildSegmentTree(int treeIndex, int l, int r) {
  14. if (l == r) {
  15. tree[treeIndex] = data[l];
  16. return;
  17. }
  18. int leftTreeIndex = leftChild(treeIndex);
  19. int rightTreeIndex = rightChild(treeIndex);
  20. int min = (l + r) / 2;
  21. buildSegmentTree(leftTreeIndex, l, min);
  22. buildSegmentTree(rightTreeIndex, min + 1, r);
  23. tree[treeIndex] = merge.merge(tree[leftTreeIndex], tree[rightTreeIndex]);
  24. }
  25. @Override
  26. public String toString() {
  27. StringBuilder res = new StringBuilder();
  28. res.append("[");
  29. for (int i = 0; i < tree.length; i++) {
  30. if (tree[i] == null) {
  31. res.append("null");
  32. } else {
  33. res.append(tree[i]);
  34. }
  35. if (i != tree.length - 1) {
  36. res.append(", ");
  37. }
  38. }
  39. res.append("]");
  40. return res.toString();
  41. }
五、线段树的查询

</>复制代码

  1. // 线段树的查询操作,区间[queryL, queryR]
  2. public E query(int queryL, int queryR) {
  3. if (queryL < 0 || queryL >= data.length || queryR < 0 || queryR >= data.length) {
  4. throw new IllegalArgumentException("queryL or queryR is illegal");
  5. }
  6. return query(0, 0, data.length - 1, queryL, queryR);
  7. }
  8. // 递归,以treeIndex为根节点,区间为[l, r],查询区间为[queryL, queryR]
  9. private E query(int treeIndex, int l, int r, int queryL, int queryR) {
  10. if (l == queryL && r == queryR) {
  11. return tree[treeIndex];
  12. }
  13. int leftChildIndex = leftChild(treeIndex);
  14. int rightChildIndex= rightChild(treeIndex);
  15. int mid = (l + r) / 2;
  16. if (queryL >= mid + 1) {
  17. return query(rightChildIndex, mid + 1, r, queryL, queryR);
  18. } else if (queryR <= mid) {
  19. return query(leftChildIndex, l, mid, queryL, queryR);
  20. }
  21. E left = query(leftChildIndex, l, mid, queryL, mid);
  22. E right = query(rightChildIndex, mid + 1, r, mid + 1, queryR);
  23. return merge.merge(left, right);
  24. }
六、LeetCode上303号问题

题目:303. 区域和检索 - 数组不可变
描述:给定一个整数数组 nums,求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和,包含 i, j 两点。
示例:

</>复制代码

  1. 给定 nums = [-2, 0, 3, -5, 2, -1],求和函数为 sumRange()
  2. sumRange(0, 2) -> 1
  3. sumRange(2, 5) -> -1
  4. sumRange(0, 5) -> -3

解题代码:

</>复制代码

  1. // 注意,如果要在leetcode上提交解答,必须把Merge接口和SegmentTree类的代码一并提交,这里并没有在写NumArray类中
  2. public class NumArray {
  3. private SegmentTree segTree;
  4. public NumArray(int[] nums) {
  5. if (nums.length > 0) {
  6. Integer[] data = new Integer[nums.length];
  7. for (int i = 0; i < nums.length; i++) {
  8. data[i] = nums[i];
  9. }
  10. segTree = new SegmentTree<>(data, (a, b) -> a + b);
  11. }
  12. }
  13. public int sumRange(int i, int j) {
  14. if (segTree == null) {
  15. throw new IllegalArgumentException("segment tree is null");
  16. }
  17. return segTree.query(i, j);
  18. }
  19. }
七、线段树的更新

</>复制代码

  1. public void set(int index, E e) {
  2. if (index < 0 || index >= data.length) {
  3. throw new IllegalArgumentException("index is illegal");
  4. }
  5. set(0, 0, data.length - 1, index, e);
  6. }
  7. private void set(int treeIndex, int l, int r, int index, E e) {
  8. if (l == r) {
  9. tree[treeIndex] = e;
  10. return;
  11. }
  12. int leftChildIndex = leftChild(treeIndex);
  13. int rightChildIndex= rightChild(treeIndex);
  14. int mid = (l + r) / 2;
  15. if (index >= mid + 1) {
  16. set(rightChildIndex, mid + 1, r, index, e);
  17. } else if (index <= mid) {
  18. set(leftChildIndex, l, mid, index, e);
  19. }
  20. tree[treeIndex] = merge.merge(tree[leftChildIndex], tree[rightChildIndex]);
  21. }
八、LeetCode上307号问题

题目:307. 区域和检索 - 数组可修改
描述:给定一个整数数组 nums,求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和,包含 i, j 两点。
示例:

</>复制代码

  1. Given nums = [1, 3, 5]
  2. sumRange(0, 2) -> 9
  3. update(1, 2)
  4. sumRange(0, 2) -> 8

解题代码:

</>复制代码

  1. class NumArray {
  2. // 注意,如果要在leetcode上提交解答,必须把Merge接口和SegmentTree类的代码一并提交,这里并没有在写NumArray类中
  3. private SegmentTree segTree;
  4. public NumArray(int[] nums) {
  5. if (nums.length > 0) {
  6. Integer[] data = new Integer[nums.length];
  7. for (int i = 0; i < nums.length; i++) {
  8. data[i] = nums[i];
  9. }
  10. segTree = new SegmentTree<>(data, (a, b) -> a + b);
  11. }
  12. }
  13. public void update(int i, int val) {
  14. if (segTree == null) {
  15. throw new IllegalArgumentException("segment tree is null");
  16. }
  17. segTree.set(i, val);
  18. }
  19. public int sumRange(int i, int j) {
  20. if (segTree == null) {
  21. throw new IllegalArgumentException("segment tree is null");
  22. }
  23. return segTree.query(i, j);
  24. }
  25. }

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/71998.html

相关文章

  • 理解数据结构)—— 线段SegmentTree

    摘要:示例解题代码注意,如果要在上提交解答,必须把接口和类的代码一并提交,这里并没有在写类中 我理解的数据结构(八)—— 线段树(SegmentTree) 一、什么是线段树 1.最经典的线段树问题:区间染色有一面墙,长度为n,每次选择一段墙进行染色,m次操作后,我们可以看见多少种颜色?m次操作后,我们可以在[i, j]区间内看见多少种颜色?showImg(https://segmentfau...

    shaonbean 评论0 收藏0
  • LuxTdmZtIC

    摘要:转载史上最简单的平衡树无旋作者博客地址使用此文件时请保留上述信息谢谢合作觉得文章不错请点击链接为博客点赞高能预警所有示例代码都是数组版的欢迎前置知识线段树请确保你完全理解最基础的线段树和区间加法和区间求和一简介无旋又称是范浩强大佬发明的一种 【转载】史上最简单的平衡树——无旋Treap showImg(https://segmentfault.com/img/bVbuWGu?w=60...

    CoffeX 评论0 收藏0
  • LuxTdmZtIC

    摘要:转载史上最简单的平衡树无旋作者博客地址使用此文件时请保留上述信息谢谢合作觉得文章不错请点击链接为博客点赞高能预警所有示例代码都是数组版的欢迎前置知识线段树请确保你完全理解最基础的线段树和区间加法和区间求和一简介无旋又称是范浩强大佬发明的一种 【转载】史上最简单的平衡树——无旋Treap showImg(https://segmentfault.com/img/bVbuWGu?w=60...

    tuantuan 评论0 收藏0
  • LuxTdmZtIC

    摘要:转载史上最简单的平衡树无旋作者博客地址使用此文件时请保留上述信息谢谢合作觉得文章不错请点击链接为博客点赞高能预警所有示例代码都是数组版的欢迎前置知识线段树请确保你完全理解最基础的线段树和区间加法和区间求和一简介无旋又称是范浩强大佬发明的一种 【转载】史上最简单的平衡树——无旋Treap showImg(https://segmentfault.com/img/bVbuWGu?w=60...

    roundstones 评论0 收藏0
  • 【转载】史上最简单平衡——无旋Treap

    摘要:转载史上最简单的平衡树无旋作者博客地址使用此文件时请保留上述信息谢谢合作觉得文章不错请点击链接为博客点赞高能预警所有示例代码都是数组版的欢迎前置知识线段树请确保你完全理解最基础的线段树和区间加法和区间求和一简介无旋又称是范浩强大佬发明的一种 【转载】史上最简单的平衡树——无旋Treap 作者:fzszkl 博客地址:https://ac.nowcoder.com/discu... ...

    崔晓明 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<