Java数据结构之线段树详解
作者:strongmore 发布时间:2022-09-03 08:13:32
标签:Java,线段树
介绍
线段树(又名区间树)也是一种二叉树,每个节点的值等于左右孩子节点值的和,线段树示例图如下
以求和为例,根节点表示区间0-5的和,左孩子表示区间0-2的和,右孩子表示区间3-5的和,依次类推。
代码实现
/**
* 使用数组实现线段树
*/
public class SegmentTree<E> {
private Node[] data;
private int size;
private Merger<E> merger;
public SegmentTree(E[] source, Merger<E> merger) {
this.merger = merger;
this.size = source.length;
this.data = new Node[size * 4];
buildTree(0, source, 0, size - 1);
}
public E search(int queryLeft, int queryRight) {
if (queryLeft < 0 || queryLeft > size || queryRight < 0 || queryRight > size
|| queryLeft > queryRight) {
throw new IllegalArgumentException("index is illegal");
}
return search(0, queryLeft, queryRight);
}
/**
* 查询区间queryLeft-queryRight的值
*/
private E search(int treeIndex, int queryLeft, int queryRight) {
Node treeNode = data[treeIndex];
int left = treeNode.left;
int right = treeNode.right;
if (left == queryLeft && right == queryRight) {
return elementData(treeIndex);
}
int leftTreeIndex = leftChild(treeIndex);
int rightTreeIndex = rightChild(treeIndex);
int middle = left + ((right - left) >> 1);
if (queryLeft > middle) {
return search(rightTreeIndex, queryLeft, queryRight);
} else if (queryRight <= middle) {
return search(leftTreeIndex, queryLeft, queryRight);
}
E leftEle = search(leftTreeIndex, queryLeft, middle);
E rightEle = search(rightTreeIndex, middle + 1, queryRight);
return merger.merge(leftEle, rightEle);
}
public void update(int index, E e) {
update(0, index, e);
}
/**
* 更新索引为index的值为e
*/
private void update(int treeIndex, int index, E e) {
Node treeNode = data[treeIndex];
int left = treeNode.left;
int right = treeNode.right;
if (left == right) {
treeNode.data = e;
return;
}
int leftTreeIndex = leftChild(treeIndex);
int rightTreeIndex = rightChild(treeIndex);
int middle = left + ((right - left) >> 1);
if (index > middle) {
update(rightTreeIndex, index, e);
} else {
update(leftTreeIndex, index, e);
}
treeNode.data = merger.merge(elementData(leftTreeIndex), elementData(rightTreeIndex));
}
private void buildTree(int treeIndex, E[] source, int left, int right) {
if (left == right) {
data[treeIndex] = new Node<>(source[left], left, right);
return;
}
int leftTreeIndex = leftChild(treeIndex);
int rightTreeIndex = rightChild(treeIndex);
int middle = left + ((right - left) >> 1);
buildTree(leftTreeIndex, source, left, middle);
buildTree(rightTreeIndex, source, middle + 1, right);
E treeData = merger.merge(elementData(leftTreeIndex), elementData(rightTreeIndex));
data[treeIndex] = new Node<>(treeData, left, right);
}
@Override
public String toString() {
return Arrays.toString(data);
}
private E elementData(int index) {
return (E) data[index].data;
}
private int leftChild(int index) {
return index * 2 + 1;
}
private int rightChild(int index) {
return index * 2 + 2;
}
private static class Node<E> {
E data;
int left;
int right;
Node(E data, int left, int right) {
this.data = data;
this.left = left;
this.right = right;
}
@Override
public String toString() {
return String.valueOf(data);
}
}
public interface Merger<E> {
E merge(E e1, E e2);
}
}
我们以LeetCode上的一个问题来分析线段树的构建,查询和更新,LeetCode307问题如下:
给定一个整数数组,查询索引区间[i,j]的元素的总和。
线段树构建
private void buildTree(int treeIndex, E[] source, int left, int right) {
if (left == right) {
data[treeIndex] = new Node<>(source[left], left, right);
return;
}
int leftTreeIndex = leftChild(treeIndex);
int rightTreeIndex = rightChild(treeIndex);
int middle = left + ((right - left) >> 1);
buildTree(leftTreeIndex, source, left, middle);
buildTree(rightTreeIndex, source, middle + 1, right);
E treeData = merger.merge(elementData(leftTreeIndex), elementData(rightTreeIndex));
data[treeIndex] = new Node<>(treeData, left, right);
}
测试代码
public class Main {
public static void main(String[] args) {
Integer[] nums = {-2, 0, 3, -5, 2, -1};
SegmentTree<Integer> segmentTree = new SegmentTree<>(nums, Integer::sum);
System.out.println(segmentTree);
}
}
最后构造出的线段树如下,前面为元素值,括号中为包含的区间。
递归构造过程为
当左指针和右指针相等时,表示为叶子节点
将左孩子和右孩子值相加,构造当前节点,依次类推
区间查询
/**
* 查询区间queryLeft-queryRight的值
*/
private E search(int treeIndex, int queryLeft, int queryRight) {
Node treeNode = data[treeIndex];
int left = treeNode.left;
int right = treeNode.right;
if (left == queryLeft && right == queryRight) {
return elementData(treeIndex);
}
int leftTreeIndex = leftChild(treeIndex);
int rightTreeIndex = rightChild(treeIndex);
int middle = left + ((right - left) >> 1);
if (queryLeft > middle) {
return search(rightTreeIndex, queryLeft, queryRight);
} else if (queryRight <= middle) {
return search(leftTreeIndex, queryLeft, queryRight);
}
E leftEle = search(leftTreeIndex, queryLeft, middle);
E rightEle = search(rightTreeIndex, middle + 1, queryRight);
return merger.merge(leftEle, rightEle);
}
查询区间2-5的和
public class Main {
public static void main(String[] args) {
Integer[] nums = {-2, 0, 3, -5, 2, -1};
SegmentTree<Integer> segmentTree = new SegmentTree<>(nums, Integer::sum);
System.out.println(segmentTree);
System.out.println(segmentTree.search(2, 5)); // -1
}
}
查询过程为
待查询的区间和当前节点的区间相等,返回当前节点值
待查询左区间大于中间区间值,查询右孩子
待查询右区间小于中间区间值,查询左孩子
待查询左区间在左孩子,右区间在右孩子,两边查询结果相加
更新
/**
* 更新索引为index的值为e
*/
private void update(int treeIndex, int index, E e) {
Node treeNode = data[treeIndex];
int left = treeNode.left;
int right = treeNode.right;
if (left == right) {
treeNode.data = e;
return;
}
int leftTreeIndex = leftChild(treeIndex);
int rightTreeIndex = rightChild(treeIndex);
int middle = left + ((right - left) >> 1);
if (index > middle) {
update(rightTreeIndex, index, e);
} else {
update(leftTreeIndex, index, e);
}
treeNode.data = merger.merge(elementData(leftTreeIndex), elementData(rightTreeIndex));
}
更新只影响元素值,不影响元素区间。
更新其实和构建的逻辑类似,找到待更新的实际索引,依次更新父节点的值。
来源:https://www.cnblogs.com/strongmore/p/14223224.html
0
投稿
猜你喜欢
- 我想,对于各位使用面向对象编程语言的程序员来说,“接口”这个名词一定不陌生,但是不知各位有没有这样的疑惑:接口有什么用途?它和抽象类有什么区
- 参考链接IDEA 2020.2.3版本IntelliJ IDEA 2020.2.3永久激活码(亲测有效)IDEA 2019.3版本Intel
- 一、获取程序集版本 程序代码 label版本.Text = System.Reflection.Assembly.GetExecutingA
- SmartArt其实就是一个文字的可视化工具,用户可在PowerPoint,Word,Excel中使用该特性创建各种图形图表。SmartAr
- 目录一、简述二、内容一、简述利用C# TcpClient在局域网内传输文件,可是文件发送到对面的时候却要重新命名文件的。那可不可以连着文件名
- 新手练手必备~密码账户为:先创建账户类:package cn.Atm;/*** @author 偶my耶*/import java.io.*
- 打注解@SpringBootTest的时候不会出现提示但是又导入了 <dependency> &nb
- 本文实例讲述了Android编程之Sdcard相关代码。分享给大家供大家参考,具体如下:1. 检测Sdcard是否可用:public sta
- 1,获取当前线程信息Thread.CurrentThread 是一个 静态的 Thread 类,Thread 的CurrentTh
- 在Spring中有一个类CachingUserDetailsService实现了UserDetailsService接口,该类使用静态代理模
- 前言最近因为同事bean配置的问题导致生产环境往错误的redis实例写入大量的数据,差点搞挂redis。经过快速的问题定位,发现是同事新增一
- 用c#中创建一个windows服务非常简单,与windows服务相关的类都在System.ServiceProcess命名空间下。每个服务都
- 部分情况下无法通过maven仓库直接下载需要的jar包,只能讲jar包下载至本地来使用,spring boot框架内通过maven加载第三方
- 1. json数据类型类型描述Number数字型String字符串型Boolean布尔型Array数组Object对象null空值(1)js
- 前言很多人之前编写Java代码都是用的Eclipse,确实Eclipse是一个很好的工具,熟悉了之后用起来很方便,但是没办法,很多公司都强制
- 解决库存扣减及订单创建时防止并发死锁的问题在我们日常开发的过程可有会遇到以下错误事务(进程 ID 82)与另一个进程被死锁在 锁 资源上,并
- springmvc 使用map接收参数开发过程中有时候我们并不知道前端都会传递哪些参数给到后端. 为方便扩展接口功能, 在请求参数不改变的情
- 直接来,RequestDemo5代码,get请求和post请求都请求转发了,转发到RequestDemo6请求 RequestDe
- /// <summary>/// 固定长度的随机字符串/// </summary>/// <param nam
- 在一个完整的项目中,如果每一个控制器的方法都返回不同的结果,那么对项目的维护和扩展都会很麻烦;并且现在主流的开发模式时前后端分离的模式,如果