【数据结构】了解线段树与操作线段树的基本方法

简介: 【数据结构】了解线段树与操作线段树的基本方法

线段树与操作线段树的基本方法

认识线段树

序列 【1,4,2,3】


给序列的第i个数,加上X A[i]=A[I]+X O(1)

取序列的最大的数,遍历最大值 O(N)

遍历的时候 时间复杂度高,怎么处理呢?

线段树Segment Tree


“区间” 线段树是根据区间的性质来构造的

2.png



特点:


每次将区间的长度一分为二,区间存储的左右边界 [[start,end]/[left,right]]


如果假设数组的长度 = n 线段树的高度就是 log(n)


将区间中的最大值加入进来,线段树加入值之后就是如下状态


除此之外,可以存储的区间内的最小值,区间求和等等


线段树的节点个数为 n+n/2+n/4… = (1+1/2+1/4…)*n ≈ 2n


构造线段树的时间复杂度和空间复杂度均为 O(n)

3.png



线段树创建代码实现

package com.hyc.DataStructure.SegmentTree;
/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.SegmentTree
 * @className: SegmentTree
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2022/2/26 10:15
 * @version: 1.0
 */
public class SegmentTree {
    @Override
    public String toString() {
        return "SegmentTree{" +
                "start=" + start +
                ", end=" + end +
                ", val=" + val +
                ", left=" + left +
                ", right=" + right +
                '}';
    }
    public static void main(String[] args) {
        int[] arr = {1, 4, 2, 3};
        SegmentTree root = SegmentTree.build(arr);
        System.out.println(root);
    }
    //节点区间范围
    public int start, end;
    //    存储节点值
    public int val;
    //    左右子树
    public SegmentTree left;
    public SegmentTree right;
    public SegmentTree(int start, int end, int val) {
        this.start = start;
        this.end = end;
        this.val = val;
    }
    public static SegmentTree build(int[] A) {
        return buildByRecu(0, A.length - 1, A);
    }
    public static SegmentTree buildByRecu(int start, int end, int[] A) {
        if (start > end) {
            return null;
        }
        SegmentTree root = new SegmentTree(start, end, A[start]);
        //    如果是叶子节点 直接返回
        if (start == end) {
            return root;
        }
        //    如果不是那么就以二分的形式来递归创建树
        int mid = (start + end) / 2;
        root.left = buildByRecu(start, mid, A);
        root.right = buildByRecu(mid + 1, end, A);
        //求出区间内最大值为父节点的val
        root.val = Math.max(root.left.val, root.right.val);
        return root;
    }
}

单点更新

public static void modify(SegmentTree root, int index, int value) {
        //    先找到叶子节点,然后逐渐上层
        if (root.start == root.end && root.start == index) {
            root.val = value;
            return;
        }
        int mid = (root.start + root.end) / 2;
        //    判断index 在左子树的区间,还是 右子树的区间,二分思路
        if (index <= mid) {
            modify(root.left, index, value);
            root.val = Math.max(root.left.val, root.right.val);
            return;
        }
        modify(root.right, index, value);
        root.val = Math.max(root.left.val, root.right.val);
    }


搜索线段树

搜索线段树返回索引值

public static int searchByIndex(SegmentTree root, int index) {
        //    先找到叶子节点,然后逐渐上层
        if (root.start == root.end && root.start == index) {
            return root.val;
        }
        int mid = (root.start + root.end) / 2;
        //    判断index 在左子树的区间,还是 右子树的区间,二分思路
        if (index <= mid) {
            searchByIndex(root.left, index);
            return root.val;
        }
        searchByIndex(root.right, index);
        return root.val;
    }



相关文章
|
1月前
|
Java C++ 索引
让星星⭐月亮告诉你,LinkedList和ArrayList底层数据结构及方法源码说明
`LinkedList` 和 `ArrayList` 是 Java 中两种常见的列表实现。`LinkedList` 基于双向链表,适合频繁的插入和删除操作,但按索引访问元素效率较低。`ArrayList` 基于动态数组,支持快速随机访问,但在中间位置插入或删除元素时性能较差。两者均实现了 `List` 接口,`LinkedList` 还额外实现了 `Deque` 接口,提供了更多队列操作。
23 3
|
1月前
|
存储 算法 Java
数据结构与算法学习八:前缀(波兰)表达式、中缀表达式、后缀(逆波兰)表达式的学习,中缀转后缀的两个方法,逆波兰计算器的实现
前缀(波兰)表达式、中缀表达式和后缀(逆波兰)表达式的基本概念、计算机求值方法,以及如何将中缀表达式转换为后缀表达式,并提供了相应的Java代码实现和测试结果。
51 0
数据结构与算法学习八:前缀(波兰)表达式、中缀表达式、后缀(逆波兰)表达式的学习,中缀转后缀的两个方法,逆波兰计算器的实现
|
1月前
|
存储 编译器 C++
【初阶数据结构】掌握二叉树遍历技巧与信息求解:深入解析四种遍历方法及树的结构与统计分析
【初阶数据结构】掌握二叉树遍历技巧与信息求解:深入解析四种遍历方法及树的结构与统计分析
|
1月前
|
存储
ES6中的Set数据结构的常用方法和使用场景
ES6中的Set数据结构的常用方法和使用场景
|
1月前
|
存储 算法 索引
HashMap底层数据结构及其增put删remove查get方法的代码实现原理
HashMap 是基于数组 + 链表 + 红黑树实现的高效键值对存储结构。默认初始容量为16,负载因子为0.75。当存储元素超过容量 * 负载因子时,会进行扩容。HashMap 使用哈希算法计算键的索引位置,通过链表或红黑树解决哈希冲突,确保高效存取。插入、获取和删除操作的时间复杂度接近 O(1)。
29 0
|
1月前
|
算法 Java C语言
【数据结构】后缀(逆波兰)表达式的计算以及中缀转后缀的方法
【数据结构】后缀(逆波兰)表达式的计算以及中缀转后缀的方法
35 0
|
3月前
|
存储 算法 测试技术
【初阶数据结构篇】实现顺序结构二叉树(堆的实现方法)
注意传过去的参数是插入的位置,即插入前的size,在调整完后再将size++
25 0
|
5月前
|
存储 测试技术
【数据结构】操作受限的线性表,栈的具体实现
【数据结构】操作受限的线性表,栈的具体实现
60 5
|
5月前
|
存储 测试技术
【数据结构】操作受限的线性表,队列的具体实现
【数据结构】操作受限的线性表,队列的具体实现
45 4
|
5月前
|
存储 JavaScript 前端开发
JavaScript中的对象是数据结构,存储键值对,键为字符串,值可为任意类型,包括函数(作为方法)
【6月更文挑战第25天】JavaScript中的对象是数据结构,存储键值对,键为字符串,值可为任意类型,包括函数(作为方法)。
40 2