数据结构-线段树_什么是满线段树-程序员宅基地

技术标签: 线段树  java数据结构  

 如上图:

线段树是一颗满二叉树,叶子节点如果没有值,用null表示。 非空叶子节点就是基础数据,树中每个父亲节点代表左右孩子的结果集(比如求合,最大值,最小值等,自己定义算法,传入左右孩子即可)。

那么有n个元素,构建线段树需要开辟多少空间?

对于满二叉树,每一层节点数量都是前面所有节点数量之和+1。 也就是说,如果最后一层有n个节点,整棵树就约为2n个节点。

如果此时n为2的k次方,所有元素刚好在最后一层,整棵树约就是2n。   如果再多一个元素,就需要开辟下一层空间,如上图那样,整棵树就需要开辟4n的空间。

构建线段树:

使用两个数组来构建线段树,一个数组表示原始数据,另一个数组表示线段树。

如上图所示,如果传入一个数组,如何把它构建为线段树? 

public class SegmentTree<E> {
    //存储数据
    private E[] data;
    //用数组表示树结构
    private E[] tree;
    //定义算法类,计算左右孩子的结果。 此例中为求合
    private Merger<E> merger;

    //外界传入一个数组arr,将它构建为线段树(每个树节点就是左右孩子的和)
    public SegmentTree(E[] arr, Merger<E> merger) {
        this.merger = merger;
        data = (E[]) new Object[arr.length];
        for (int i = 0; i < arr.length; i++) {
            data[i] = arr[i];
        }
        tree = (E[]) new Object[4 * arr.length];
        buildSegmentTree(0, 0, arr.length - 1);
    }

    // 在treeIndex的位置创建表示区间[l...r]的线段树
    private void buildSegmentTree(int treeIndex, int l, int r) {
        if (l == r) {
            tree[l] = data[l];
            return;
        }
        int leftTreeIndex = leftChild(treeIndex);
        int rightTreeIndex = rightChild(treeIndex);

        int mid = (l + r) / 2;
//        int mid = l + (r - l) / 2;
        buildSegmentTree(leftTreeIndex, l, mid);
        buildSegmentTree(rightTreeIndex, mid + 1, r);
        tree[treeIndex] = merger.merge(tree[leftTreeIndex], tree[rightTreeIndex]);
    }

    // 返回完全二叉树的数组表示中,一个索引所表示的元素的左孩子节点的索引
    private int leftChild(int index) {
        return 2 * index + 1;
    }

    // 返回完全二叉树的数组表示中,一个索引所表示的元素的右孩子节点的索引
    private int rightChild(int index) {
        return 2 * index + 2;
    }

    public int getSize() {
        return data.length;
    }

    public E get(int index) {
        if (index < 0 || index >= data.length) {
            throw new IllegalArgumentException("Index is illegal.");
        }
        return data[index];
    }

    // 返回区间[queryL, queryR]的值
    public E query(int queryL, int queryR) {

        if (queryL < 0 || queryL >= data.length ||
                queryR < 0 || queryR >= data.length || queryL > queryR) {
            throw new IllegalArgumentException("Index is illegal.");
        }

        return query(0, 0, data.length - 1, queryL, queryR);
    }

    // 在以treeIndex为根的线段树中[l...r]的范围里,搜索区间[queryL...queryR]的值
    private E query(int treeIndex, int l, int r, int queryL, int queryR) {
        if (l == queryL && r == queryR) {
            return tree[treeIndex];
        }
        int leftTreeIndex = leftChild(treeIndex);
        int rightTreeIndex = rightChild(treeIndex);
        int mid = (l + r) / 2;
        if (queryL >= mid + 1) {
            return query(rightTreeIndex, mid + 1, r, queryL, queryR);
        } else if (queryR <= mid) {
            return query(leftTreeIndex, l, mid, queryL, queryR);
        }
        E leftResult = query(leftTreeIndex, l, mid, queryL, mid);
        E rightResult = query(rightTreeIndex, mid + 1, r, mid + 1, queryR);
        return merger.merge(leftResult, rightResult);
    }

// 将index位置的值,更新为e
    public void set(int index, E e) {
        if (index < 0 || index >= data.length) {
            throw new IllegalArgumentException("Index is illegal");
        }
        //直接把数据数组中对应的值改掉
        data[index] = e;
        //重构线段树
        set(0, 0, data.length - 1, index, e);
    }

    // 在以treeIndex为根的线段树中更新index的值为e
    private void set(int treeIndex, int l, int r, int index, E e) {
        //说明找到树中最底层那个节点了
        if (l == r) {
            tree[treeIndex] = e;
            return;
        }
        int mid = (l + r) / 2;
        int leftTreeIndex = leftChild(treeIndex);
        int rightTreeIndex = rightChild(treeIndex);
        if (index > mid) {
            set(rightTreeIndex, mid + 1, r, index, e);
        } else {
            set(leftTreeIndex, l, mid, index, e);
        }
        tree[treeIndex] = merger.merge(tree[leftTreeIndex], tree[rightTreeIndex]);
    }
}
public interface Merger<E> {

    /**
     * 计算两个节点的结果集
     * @param a
     * @param b
     * @return
     */
    E merge(E a, E b);
}

做一道题:

/**
 * 给你一个数组 nums ,请你完成两类查询,其中一类查询要求更新数组下标对应的值,另一类查询要求返回数组中某个范围内元素的总和。
 * <p>
 * 实现 NumArray 类:
 * <p>
 * NumArray(int[] nums) 用整数数组 nums 初始化对象 void update(int index, int val) 将 nums[index] 的值更新为 val int sumRange(int left,
 * int right) 返回子数组 nums[left, right] 的总和(即,nums[left] + nums[left + 1], ..., nums[right])
 * <p>
 * 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/range-sum-query-mutable 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
 */
public class NumArray {

    private SegmentTree<Integer> tree;

    public NumArray(int[] nums) {
        if (nums.length != 0) {
            Integer[] data = new Integer[nums.length];
            for (int i = 0; i < nums.length; i++) {
                data[i] = nums[i];
            }
            tree = new SegmentTree<Integer>(data, (a, b) -> a + b);
        }

    }

    public void update(int i, int val) {
        tree.set(i,val);
    }

    public int sumRange(int i, int j) {
       return tree.query(i,j);
    }
}

 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/growing_duck/article/details/121493314

智能推荐

mini2440 简单按键中断模式驱动程序_make -c $(kern_dir) m=`pwd` modules clean-程序员宅基地

文章浏览阅读853次。MakefileKERN_DIR = /home/grh/kernel_source_code/linux-2.6.32.2all : make -C $(KERN_DIR) M=`pwd` modules arm-linux-gcc key_interrupt_app.c -o key_interrupt_appclean : make -C $(KERN_DIR) M=`pwd_make -c $(kern_dir) m=`pwd` modules clean

subprocess.Popen BrokenPipeError: [Errno 32] Broken pipe-程序员宅基地

文章浏览阅读5.1k次,点赞3次,收藏9次。BrokenPipeError: [Errno 32] Broken pipe在向管道中写入参数的时候,一段时间正常写入数据后,若长时间未写入数据,则会报错BrokenPipeError: [Errno 32] Broken pipe,且该进程会进入睡眠原代码 # 定义管道及ffmpeg命令,输出rtmp流的时候使用command = ['ffmpeg', '-y', '-v', '24', # 日志显示等级 '-f', 'rawv_brokenpipeerror: [errno 32] broken pipe

身价1亿日元的“机器人观音”问世,为普罗大众讲解佛义 ...-程序员宅基地

文章浏览阅读81次。只有人们想不到的,没有机器人做不到的。 日前,日本高台寺展示了智能机器人观音“Minder”,旨在向现代人简单易懂的阐明佛教的教义。 据了解,“Minder”由大阪大学教授石黑浩等人协助研发,研发费用为1亿日元(约600万人民币)。外形方面,“Minder”高约195厘米、重约60公斤,头部、手臂和躯体可以转动,左眼内装有摄像头。 研究..._养猪起家身价1296亿

pandas获得指定行_pandas取dataframe特定行/列_pandas选取特定值所在的行-程序员宅基地

文章浏览阅读1.6w次,点赞13次,收藏96次。转自他人博客:https://blog.csdn.net/weixin_39586825/article/details/1117585061.按列取、按索引/行取、按特定行列取import numpy as npfrom pandas import DataFrameimport pandas as pddf=DataFrame(np.arange(12).reshape((3,4)),index=[‘one’,‘two’,‘thr’],columns=list(‘abcd’))df[‘a’]_pandas选取特定值所在的行

webgl——进入三维世界(模型矩阵、视图矩阵、投影矩阵)(六)_webgl投影矩阵推导-程序员宅基地

文章浏览阅读1.5k次,点赞5次,收藏8次。文章目录前言一、视点和视线二、投影矩阵前言本篇继续前面文章来讲解投影矩阵相关内容。一、视点和视线二、投影矩阵_webgl投影矩阵推导

Java多线程编程学习笔记 synchronized的理解 原子操作 actomic compareAndSet_compareandset 多线程原子 递增-程序员宅基地

文章浏览阅读3.4k次。Java多线程编程学习笔记 原子操作原子概念原子,是一种很小的粒子,可以理解,不是成功就是失败关键字:synchronized、Atomic系列、compareAndSet、volatile 1. 丌会被线程调度机制打断的操作,对于其它线程而言,看不到中间态,非成功即失败, 比如int a = 1是原子操作 2. long b = 1L丌一定是原子操作,跟系统位数_compareandset 多线程原子 递增

随便推点

计算机系统课程 笔记总结 CSAPP第七章 链接(7.1-7.13)_csapp 7.6.1-程序员宅基地

文章浏览阅读2.6k次,点赞16次,收藏45次。GitHub计算机系统CSAPP课程资源 计算机系统课程 笔记总结 CSAPP第二章 信息的表示和处理(2.1-2.2) 计算机系统课程 笔记总结 CSAPP第二章 信息的表示和处理(2.3-2.4) 计算机系统课程 笔记总结 CSAPP第三章 程序的机器级表示(3.2-3.4) 计算机系统课程 笔记总结 CSAPP第三章 程序的机器级表示(3.5-3.7) 计算机系统课程 笔记总结 ..._csapp 7.6.1

Redis总结-程序员宅基地

文章浏览阅读248次。目录概述Redis是什么?简述它的优缺点?为什么要使用Redis/缓存Redis为什么这么快?Redis相比Memcached有哪些优势?Redis的常用场景有哪些?数据类型Redis的数据类型有哪些?线程模型Redis为何选择单线程?Redis真的是单线程?Redisv6.0为何引入多线程?过期键的删除策略Redis过期键的删除策略?过期键的删除策略都有哪些?内存相关MySQL里有2000w数据,redis中只能存20w的数据,如何保证redis中的数据都是热点数据?Redis内存淘汰机制?Redis如何

nginx平滑重启和升级-程序员宅基地

文章浏览阅读77次。平滑重启 kill -HUP `cat /usr/local/www/nginx/logs/nginx.pid`平滑升级nginxcd /yujialinwget http://nginx.org/download/nginx-1.0.6.tar.gztar zxvf nginx-1.0.6.tar.gzcd nginx-1.0.6/usr/local/www/nginx/sbin/nginx -..._php 平滑升级

什么是ip6-程序员宅基地

文章浏览阅读3.9k次。相比于IPv4来说,IPv6的地址更加充足,安全性也更高,可以解决如今IP地址枯竭的问题,为物联网时代的发展提供网络基础;Pv6具有更大的地址空间,使用更小的路由表,加入了对自动配置的支持。ipv6是什么Pv6是第六代互联网协议,被设计用于替代使用了30多年的第四代互联网协议的下一代IP协议。由于IPv4最大的问题在于网络地址资源有限,严重制约了互联网的应用和发展,所以出现了替代版本的IP协议。..._ip6

android bluetooth stack-enable_android bluetooth stack-enable-程序员宅基地

文章浏览阅读2.5k次。android bluetooth stack_android bluetooth stack-enable

【面试分享】今日头条Java面试题,已拿offer,附答案!-程序员宅基地

文章浏览阅读960次。2021年,字节的技术岗依旧是最香的,而且随着字节的规模不断扩大,机会也越来越多。马上迎来金三银四,很多小伙伴都在撸题备战中。下面是1月份最新的头条面经,我们来看看今年大厂的Java面试主要考察哪些点。文末还有头条面试官总结的Java面试题,希望大家了解并掌握这些知识点,争取通过每一轮面试!技术一面TCP相关基础知识问题1: 请详细描述三次握手和四次挥手的过程问题2: 四次挥手中TIME_WAIT状态存在的目的是什么?问题3: TCP是通过什么机制保障可靠性的?语言的相关基础知识问题1: 描

推荐文章

热门文章

相关标签