【数据结构】线段树

目录

  • 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 设置为 (start+end)/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) {
            //区间不相交,返回 0
            return 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]: 17

2.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]: 0

3.应用

(1)LeetCode 中的 307.区域和检索 - 数组可修改这题便是对线段树的具体应用,其题目如下。显然,使用上面的代码可以直接求解。

在这里插入图片描述

(2)大家可以去 LeetCode 上找相关的线段树的题目来练习,或者也可以直接查看 LeetCode 算法刷题目录 (Java) 这篇文章中的线段树章节。如果大家发现文章中的错误之处,可在评论区中指出。

4.与前缀和之间的区别

(1)线段树和前缀和是两种常见的用于解决区间查询问题的数据结构,它们有一些区别:

  • 数据结构
    • 线段树是一种二叉树结构,用于处理区间查询和更新操作。它将区间划分为不相交的子区间,并将每个子区间的信息存储在相应节点中。
    • 前缀和是一个数组,用于存储前缀和值。它通过计算数组元素累加和的方式存储数据。
  • 功能
    • 线段树可以支持多种区间查询操作,例如区间和、区间最大值、区间最小值等。它可以在 O(logN) 的时间复杂度内完成查询和更新操作。
    • 前缀和主要用于计算数组中特定区间的和。它可以在 O(1) 的时间内计算出给定区间的和,但只能处理区间和的查询。
  • 空间复杂度
    • 线段树的空间复杂度为 O(N),其中 N 是数组的大小。它需要存储整个线段树的节点。
    • 前缀和的空间复杂度为 O(N),其中 N 是数组的大小。它只需要存储一个与数组大小相等的前缀和数组。
  • 应用场景
    • 线段树通常用于解决需要频繁进行区间查询和更新操作的问题,比如计算数组的区间和、区间最大值和最小值等。
    • 前缀和通常用于解决需要频繁计算数组特定区间和的问题,比如计算子数组的和、快速判断数组中是否存在某个区间的和等。

(2)综上所述,线段树和前缀和在功能和应用场景上略有不同,选择使用哪种数据结构取决于具体的问题需求和效率要求。

有关前缀和的相关知识可以参考【数据结构】前缀和数组这篇文章。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/207628.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

算法通关村第一关—白银挑战—链表高频面试算法题—查找两个链表的第一个公共子节点

文章目录 查找两个链表的第一个公共子节点&#xff08;1&#xff09;暴力求解法&#xff08;2&#xff09;使用哈希Hash⭐&#xff08;3&#xff09;使用集合⭐ - 与Hash类似&#xff08;4&#xff09;使用栈⭐&#xff08;5&#xff09;仍有更多方法&#xff0c;作者尚未理解&…

安卓小程序与编译抓包

APK小程序渗透测试 查找bp的证书 在浏览器中打开bp代理&#xff0c;然后在网页中搜索hppps://burp 点击高级——接受风险并继续 拿到证书 将浏览器信任证书 打开设置 搜索证书——查看证书 点击导入——导入证书 证书验证成功后&#xff0c;访问网页&#xff08;吾爱破解&a…

模型层——单表操作

单表操作 一 ORM简介 查询数据层次图解&#xff1a;如果操作mysql&#xff0c;ORM是在pymysq之上又进行了一层封装 MVC或者MTV框架中包括一个重要的部分&#xff0c;就是ORM&#xff0c;它实现了数据模型与数据库的解耦&#xff0c;即数据模型的设计不需要依赖于特定的数据库…

河南省第一届职业技能大赛网络安全项目试题

河南省第一届职业技能大赛 网络安全项目试题 一、竞赛时间 总计&#xff1a;420分钟 竞赛阶段 竞赛阶段 任务阶段 竞赛任务 竞赛时间 分值 A模块 A-1 登录安全加固 240分钟 200分 A-2 Web安全加固&#xff08;Web&#xff09; A-3 流量完整性保护与事件监控&am…

韩语语法中에和로/으로区别,柯桥发音入门韩语培训学校

에和로/으로在行动的去向与到达或涉及的地点一致时&#xff0c;二者可以互换。 但是에表示到达或涉及的具体地点&#xff0c;而로/으로表示的时动作指向的方向或经过的地点。 在只表示去向而不表示具体地点时&#xff0c;只能用로/으로&#xff0c;而在只表示具体地点而不表示方…

Nginx漏洞修复

1、漏洞 去掉在请求响应头中存在的信息 Server: nginx X-Content-Type-Options: nosniff X-Frame-Options: SAMEORIGIN X-XSS-Protection: 1;modeblock 修复方法 在Nginx的配置文件中的 server 标签内增加一下配置 server_tokens off; add_header X-Frame-Options SAMEORIGIN; …

情绪咖啡亭完美收官!来最美环湖路喝一杯“治愈”咖啡

“芭比粉”的主题墙&#xff0c;橙蓝撞色的情绪日历、当下最流行的克莱因蓝咖啡亭......颜色鲜艳&#xff0c;造型吸睛的“情绪咖啡亭”互动艺术装置区与碧树蓝天、海鸥白云相呼应。春城晚报&#xff08;开屏新闻&#xff09;生活节“送服务”系列之一的“情绪咖啡亭”活动将在…

jetson nano SSH远程连接(使用MobaXterm)

文章目录 SSH远程连接1.SSH介绍2.准备工作3.连接步骤3.1 IP查询3.2 新建会话和连接 SSH远程连接 本节课的实现&#xff0c;需要将Jetson Nano和电脑保持在同一个局域网内&#xff0c;也就是连接同一个路 由器&#xff0c;通过SSH的方式来实现远程登陆。 1.SSH介绍 SSH是一种网…

字符集与编码规则

字符集 强调&#xff1a;UTF-8是编码规则&#xff0c;不是字符集 过程&#xff1a; 字符 --查表获得对应数字&#xff0c;--编码 解码---查表----获取字符 ASCII码 &#xff1a;一个字节 8bit GBK字符集&#xff08;windows系统默认使用的GBK,系统显示ANSI&#xff09; 存…

segment-anything安装教程

文章目录 一. segment-anything安装教程 一. segment-anything安装教程 官网安装说明:https://github.com/facebookresearch/segment-anything anaconda下新建一个环境 conda create -n sam python3.8激活新建的环境 conda activate sam更换conda镜像源 conda config --add ch…

如何靠掌握自己的大数据打破信息流的壁垒?

在当今数字化时代&#xff0c;打造自己的私域流量已经成为商家乃至获取竞争优势的关键手段之一。通过掌握自己的大数据&#xff0c;可以更好地了解用户需求和市场趋势&#xff0c;优化产品和服务&#xff0c;从而打破信息流的壁垒。本文将就如何通过打造自己的私域流量并掌握大…

ROS URDF集成Rviz流程

实现流程&#xff1a; 一、新建功能包&#xff0c;导入依赖 二、编写 urdf 文件 三、在 launch 文件集成 URDF 与 Rviz 四、在 Rviz 中显示机器人模型 需求&#xff1a;在 Rviz 中显示一个盒状机器人 1、创建功能包&#xff0c;导入依赖 创建一个新的功能包&#xff0c;名…

VMWare17配置自动启动虚拟机提示:无法更新“自动启动配置”,请确保存在vmAutoStart.xml文件,并且您有权写入此文件。

文章目录 配置的时候提示&#xff1a;无法更新“自动启动配置”&#xff0c;请确保存在vmAutoStart.xml文件&#xff0c;并且您有权写入此文件。需要修改vmAutoStart.xml这个文件权限对vmautostart.xml文件右键-->属性&#xff0c;选择编辑直接将完全控制的允许勾上&#xf…

工程师每日刷题 -4

文章目录 1、深度学习2、算法与数据结构2.1、暴力解法2.2、滑动窗口法 3、编程基础 1、深度学习 问题&#xff1a;CNN的本质和优势&#xff1f; CNN 本质上是一个多层感知机 (MLP)&#xff0c;其成功的原因关键在于它所采用的【稀疏连接】&#xff08;局部感受&#xff09;和…

Android Studio Giraffe | 2022.3.1

Android Gradle 插件和 Android Studio 兼容性 Android Studio 构建系统以 Gradle 为基础&#xff0c;并且 Android Gradle 插件 (AGP) 添加了几项专用于构建 Android 应用的功能。下表列出了各个 Android Studio 版本所需的 AGP 版本。 Android Studio 版本所需的 AGP 版本I…

Python+Requests模块session处理和SSL证书处理关闭警告

session处理 部分接口需要先登录网址&#xff0c;才能有权限进行调用&#xff0c;这时可以使用到session&#xff0c;具体操作是&#xff1a;先使用网站 的登录api进行登录&#xff0c;得到session后&#xff0c;然后用该session来请求其它的接口。 示例代码&#xff1a; se…

实验 elk+filebeat+kafka

kafka 3.4.1 elkfilebeatkafka 实现日志收集 httpd1 mysql1 topic 2.7 3.0 关闭防火墙 systemctl stop firewalld systemctl disable firewalld setenforce 0 安装 JDK yum install -y java-1.8.0-openjdk java-1.8.0-openjdk-devel java -version 安装 Zookeeper cd /…

C++作业3

设计一个Per类&#xff0c;类中包含私有成员:姓名、年龄、指针成员身高、体重&#xff0c;再设计一个Stu类&#xff0c;类中包含私有成员:成绩、Per类对象p1&#xff0c;设计这两个类的构造函数、析构函数和拷贝构造函数。 代码&#xff1a; #include <iostream>using n…

力扣5.最长回文子串

题目描述 思路 1.能够反复利用已判断好的回文子串 2.当子串s[i1,j-1]是回文子串时&#xff0c;只要s[i]s[j]&#xff0c;那么s[i,j]也会是回文子串 3.用好动态规划&#xff0c;具体解释在代码注释里 代码 class Solution {public String longestPalindrome(String s) {int…

【【FPGA 之Micro Blaze的串口中断实验】】

FPGA 之Micro Blaze的串口中断实验 我们在使用 MicroBlaze 进行嵌入式系统设计的时候&#xff0c;通常会用到 AXI Uartlite IP 核与外部设备通信。AXI UART IP 核实现了 RS-232 通讯协议&#xff0c;并使得大家可以设置串口通信相关的波特率、奇偶校验位、停止位和数据位等参数…