美文网首页线段树
基础九 线段树Segment Tree

基础九 线段树Segment Tree

作者: 谢谢水果 | 来源:发表于2018-12-18 05:12 被阅读0次

线段树功能：

  • O(logN) 找到某区间的 最大最小值 元素个数 区间和
  • O(1) 得到全部区间的 最大最小值 元素个数 区间和
  • O(logN) 添加或更新
    lt439 Segment Tree Build II 维持区间最大值的线段树 的创建
    lt202 Segment Tree Query 维持区间最大值的线段树 的查询
    lt203 Segment Tree Modify 维持区间最大值的线段树 的修改
    lt205 Interval Minimum Number 维持区间最大值的线段树 的创建+查询
    lt247 Segment Tree Query II 维护区间范围内元素个数的线段树 的查询
    lt206 Interval Sum 维护区间和的线段数 的创建+查询
    lt207 Interval Sum II 维护区间和的线段数 的创建+查询+修改
    lt248 Count of Smaller Number
  • 找min max
  • 在min max区间内以区间和 建线段树 开始全是零
  • 全部插入之后查询

lt249 Count of Smaller Number before itself

  • 找min max
  • 在min max区间内以区间和 建线段树 开始全是零
  • 数组从后向前调用modify插入 一边插入一边查询
    315 Count of Smaller Numbers After Self

注意：

  • 别忘记直接返回 start==end时的return

lt439 Segment Tree Build II + lt202 Segment Tree Query

/**
 * Definition of SegmentTreeNode:
 * public class SegmentTreeNode {
 *     public int start, end, max;
 *     public SegmentTreeNode left, right;
 *     public SegmentTreeNode(int start, int end, int max) {
 *         this.start = start;
 *         this.end = end;
 *         this.max = max
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param A: a list of integer
     * @return: The root of Segment Tree
     */
    public SegmentTreeNode build(int[] A) {
        // write your code here
        return helper(A, 0, A.length-1);
    }
    private SegmentTreeNode helper(int[] nums, int start, int end){
        if(start>end)
            return null;
        SegmentTreeNode result = new SegmentTreeNode(start, end, nums[start]);
        if(start==end){
            return result;
        }
        int mid = start+(end-start)/2;
        SegmentTreeNode left = helper(nums, start, mid);
        SegmentTreeNode right = helper(nums, mid+1, end);
        result.left = left;
        result.right = right;
        result.max = Math.max(left.max, right.max);
        return result;
    }
public int query(SegmentTreeNode root, int start, int end) {
        // write your code here
        if(start==root.start && end==root.end)
            return root.max;
        int mid = root.start+(root.end-root.start)/2;
        if(end<=mid){
            return query(root.left, start, end);
        }else if(start>=mid+1){
            return query(root.right, start, end);
        }else{
            return Math.max(query(root.left, start, mid), query(root.right, mid+1, end));
        }
    }
    public void modify(SegmentTreeNode root, int index, int value) {
        // write your code here
        if(root.start==index && root.end==index){
            root.max = value;
            return;
        }
        int mid = root.start+(root.end-root.start)/2;
        if(index<=mid){
            modify(root.left, index, value);
        }else{
            modify(root.right, index, value);
        }
        root.max = Math.max(root.left.max, root.right.max);
    }
}

/**
 * Definition of SegmentTreeNode:
 * public class SegmentTreeNode {
 *     public int start, end, count;
 *     public SegmentTreeNode left, right;
 *     public SegmentTreeNode(int start, int end, int count) {
 *         this.start = start;
 *         this.end = end;
 *         this.count = count;
 *         this.left = this.right = null;
 *     }
 * }
 */

####lt205 Interval Minimum Number 维持区间最大值的线段树 的创建+查询

/**

  • Definition of Interval:
  • public classs Interval {
  • int start, end;

  • Interval(int start, int end) {

  •     this.start = start;

  •     this.end = end;

  • }
  • }
    */

public class Solution {
/**
* @param A: An integer array
* @param queries: An query list
* @return: The result list
*/
class Node{
int start, end, min;
Node left, right;
Node(int start, int end, int min){
this.start = start;
this.end = end;
this.min = min;
}
}
private Node build(int[] nums, int start, int end){
if(start>end)
return null;
Node result = new Node(start, end, nums[start]);
if(start == end){
return result;
}
int mid = start+(end-start)/2;
Node left = build(nums, start, mid);
Node right = build(nums, mid+1, end);
result.left = left;
result.right = right;
result.min = Math.min(left.min, right.min);
return result;
}
private int query(int start, int end, Node root){
if(start<=root.start && end>=root.end){
return root.min;
}
int mid = root.start+(root.end-root.start)/2;
if(start>=mid+1){
return query(start, end, root.right);
}else if(end<=mid){
return query(start, end, root.left);
}else{
return Math.min(query(start, mid, root.left), query(mid+1, end, root.right));
}
}
public List<Integer> intervalMinNumber(int[] A, List<Interval> queries) {
// write your code here

    List<Integer> results = new ArrayList<>();
    if(A==null || A.length==0)
        return results;
    Node root = build(A, 0, A.length-1);
    for(Interval interval: queries){
        int result = query(interval.start, interval.end, root);
        results.add(result);
    }
    return results;
}

}

####lt247 Segment Tree Query II 维护区间范围内元素个数的线段树 的查询
public class Solution {
    /*
     * @param root: The root of segment tree.
     * @param start: start value.
     * @param end: end value.
     * @return: The count number in the interval [start, end]
     */
    public int query(SegmentTreeNode root, int start, int end) {
        // write your code here
        if(start>end || root==null)
            return 0;
        if(start<=root.start && end>=root.end){
            return root.count;
        }
        int mid = root.start+(root.end-root.start)/2;
        if(mid>=end){
            return query(root.left, start, end);
        }else if(mid+1<=start){
            return query(root.right, start, end);
        }else{
            int left = query(root.left, start, mid);
            int right = query(root.right, mid+1, end);
            return left+right;
        }
    }
}

lt206 Interval Sum 维护区间和的线段数 的创建+修改+查询

/**
 * Definition of Interval:
 * public classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 * }
 */

public class Solution {
    /**
     * @param A: An integer list
     * @param queries: An query list
     * @return: The result list
     */
    class Node{
        int start;
        int end;
        long sum;
        Node left, right;
        Node(int start, int end, long sum){
            this.start = start;
            this.end = end;
            this.sum = sum;
        }
    }
    private Node buildTree(int[] nums, int start, int end){
        if(start>end){
            return null;
        }
        Node result = new Node(start, end, (long)(nums[start]));
        if(start==end){
            return result;
        }
        int mid = start+(end-start)/2;
        Node left = buildTree(nums, start, mid);
        Node right = buildTree(nums, mid+1, end);
        result.sum = left.sum+right.sum;
        result.right = right;
        result.left = left;
        return result;
    }
    private long query(int[] nums, int start, int end, Node root){
        // if(root==null || start>root.end || end<root.start)
        if(root==null || start>end)
            return 0;
        if(start<=root.start && end>=root.end){
            return root.sum;
        }
        int mid = root.start+(root.end-root.start)/2;
        if(start>=mid+1){
            return query(nums, start, end, root.right);
        }else if(end<=mid){
            return query(nums, start, end, root.left);
        }else{
            return query(nums, start, mid, root.left)+query(nums, mid+1, end, root.right);
        }
    }
    public List<Long> intervalSum(int[] A, List<Interval> queries) {
        // write your code here
        Node root = buildTree(A, 0, A.length-1);
        List<Long> results = new ArrayList<>();
        for(Interval interval: queries){
            Long result = query(A, interval.start, interval.end, root);
            results.add(result);
        }
        return results;
    }
}

lt207 Interval Sum II 维护区间和的线段数 的创建+查询+修改

public class Solution {
    /* you may need to use some attributes here */

    /*
    * @param A: An integer array
    */
    Node root;
    public Solution(int[] A) {
        // do intialization if necessary
        root = buildTree(A, 0, A.length-1);
    }
    /*
     * @param start: An integer
     * @param end: An integer
     * @return: The sum from start to end
     */
    public long query(int start, int end) {
        // write your code here
        return queryhelper(start, end, root);
    }

    /*
     * @param index: An integer
     * @param value: An integer
     * @return: nothing
     */
    public void modify(int index, int value) {
        // write your code here
        modifyHelper(index, value, root);
    }
    
    class Node{
        int start;
        int end;
        long sum;
        Node left, right;
        Node(int start, int end, long sum){
            this.start = start;
            this.end = end;
            this.sum = sum;
        }
    }
    private Node buildTree(int[] nums, int start, int end){
        if(start>end){
            return null;
        }
        Node result = new Node(start, end, (long)(nums[start]));
        if(start==end){
            return result;
        }
        int mid = start+(end-start)/2;
        Node left = buildTree(nums, start, mid);
        Node right = buildTree(nums, mid+1, end);
        result.sum = left.sum+right.sum;
        result.right = right;
        result.left = left;
        return result;
    }
    private long queryhelper(int start, int end, Node root){
        // if(root==null || start>root.end || end<root.start)
        if(root==null || start>end)
            return 0;
        if(start<=root.start && end>=root.end){
            return root.sum;
        }
        int mid = root.start+(root.end-root.start)/2;
        if(start>=mid+1){
            return queryhelper(start, end, root.right);
        }else if(end<=mid){
            return queryhelper(start, end, root.left);
        }else{
            return queryhelper(start, mid, root.left)+queryhelper(mid+1, end, root.right);
        }
    }
    private void modifyHelper(int index, int value, Node root){
        if(root.start==index && root.end==index){
            root.sum = value;
            return;
        }
            
        int mid = root.start+(root.end-root.start)/2;
        if(index<=mid){
            modifyHelper(index, value, root.left);
        }else{
            modifyHelper(index, value, root.right);
        }
        root.sum = root.right.sum+root.left.sum;
    }
}

lt249 Count of Smaller Number before itself

public class Solution {
    /**
     * @param A: an integer array
     * @return: A list of integers includes the index of the first number and the index of the last number
     */
    public List<Integer> countOfSmallerNumberII(int[] A) {
        // write your code here
        List<Integer> results = new ArrayList<>();
        if(A==null || A.length==0){
            return results;
        }
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for(int i: A){
            min = Math.min(min, i);
            max = Math.max(max, i);
        }
        
        Node root = build(min, max);
        for(int i: A){
            int result = query(root, min, i-1);
            modify(i, root);
            results.add(result);
        }
        return results;
    }
    class Node{
        int min, max, count;
        Node left, right;
        Node(int min, int max, int count){
            this.min = min;
            this.max = max;
            this.count = count;
        }
    }
    private Node build(int min, int max){
        if(min>max){
            return null;
        }
        Node result = new Node(min, max, 0);
        if(min==max){
            return result;
        }
        int mid = min+(max-min)/2;
        Node left = build(min, mid);
        Node right = build(mid+1, max);
        result.left = left;
        result.right = right;
        return result;
    }
    private void modify(int value, Node root){
        if(value==root.min && value==root.max){
            root.count++;
            return;
        }
        int mid = root.min+(root.max-root.min)/2;
        if(value<=mid){
            modify(value, root.left);
        }else{
            modify(value, root.right);
        }
        root.count = root.left.count+root.right.count;
    }
    private int query(Node root, int min, int max){
        if(min>max)
            return 0;
        if(root.min>=min && root.max<=max){
            return root.count;
        }
        int mid = root.min+(root.max-root.min)/2;
        if(mid>=max){
            return query(root.left, min, max);
        }else if(min>=mid+1){
            return query(root.left, min, max);
        }else{
            return query(root.left, min, mid)+query(root.right, mid+1, max);
        }
    }
}

315 Count of Smaller Numbers After Self

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> result = countOfSmallerNumberII(nums);
        Collections.reverse(result);
        return result;
    }
    public List<Integer> countOfSmallerNumberII(int[] A) {
        // write your code here
        List<Integer> results = new ArrayList<>();
        if(A==null || A.length==0){
            return results;
        }
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for(int i: A){
            min = Math.min(min, i);
            max = Math.max(max, i);
        }
        
        Node root = build(min, max);
        for(int i=A.length-1; i>=0; i--){
            int result = query(root, min, A[i]-1);
            modify(A[i], root);
            results.add(result);
        }
        return results;
    }
    class Node{
        int min, max, count;
        Node left, right;
        Node(int min, int max, int count){
            this.min = min;
            this.max = max;
            this.count = count;
        }
    }
    private Node build(int min, int max){
        if(min>max){
            return null;
        }
        Node result = new Node(min, max, 0);
        if(min==max){
            return result;
        }
        int mid = min+(max-min)/2;
        Node left = build(min, mid);
        Node right = build(mid+1, max);
        result.left = left;
        result.right = right;
        return result;
    }
    private void modify(int value, Node root){
        if(value==root.min && value==root.max){
            root.count++;
            return;
        }
        int mid = root.min+(root.max-root.min)/2;
        if(value<=mid){
            modify(value, root.left);
        }else{
            modify(value, root.right);
        }
        root.count = root.left.count+root.right.count;
    }
    private int query(Node root, int min, int max){
        if(min>max)
            return 0;
        if(root.min>=min && root.max<=max){
            return root.count;
        }
        int mid = root.min+(root.max-root.min)/2;
        if(mid>=max){
            return query(root.left, min, max);
        }else if(min>=mid+1){
            return query(root.left, min, max);
        }else{
            return query(root.left, min, mid)+query(root.right, mid+1, max);
        }
    }
}

lt248 Count of Smaller Number

public class Solution {
    /**
     * @param A: An integer array
     * @param queries: The query list
     * @return: The number of element in the array that are smaller that the given integer
     */
    
    public List<Integer> countOfSmallerNumber(int[] A, int[] queries) {
        // write your code here
        List<Integer> results = new ArrayList<>();
        if(A==null || A.length==0){
            for(int i: queries){
                results.add(0);
            }
            return results;
        }
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for(int i: A){
            min = Math.min(min, i);
            max = Math.max(max, i);
        }
        
        Node root = build(min, max);
        for(int i: A){
            modify(i, root);
        }
        
        for(int q : queries){
            int result = query(root, min, q-1);
            results.add(result);
        }
        return results;
    }
    class Node{
        int min, max, count;
        Node left, right;
        Node(int min, int max, int count){
            this.min = min;
            this.max = max;
            this.count = count;
        }
    }
    private Node build(int min, int max){
        if(min>max){
            return null;
        }
        Node result = new Node(min, max, 0);
        if(min==max){
            return result;
        }
        int mid = min+(max-min)/2;
        Node left = build(min, mid);
        Node right = build(mid+1, max);
        result.left = left;
        result.right = right;
        return result;
    }
    private void modify(int value, Node root){
        if(value==root.min && value==root.max){
            root.count++;
            return;
        }
        int mid = root.min+(root.max-root.min)/2;
        if(value<=mid){
            modify(value, root.left);
        }else{
            modify(value, root.right);
        }
        root.count = root.left.count+root.right.count;
    }
    private int query(Node root, int min, int max){
        if(min>max)
            return 0;
        if(root.min>=min && root.max<=max){
            return root.count;
        }
        int mid = root.min+(root.max-root.min)/2;
        if(mid>=max){
            return query(root.left, min, max);
        }else if(min>=mid+1){
            return query(root.left, min, max);
        }else{
            return query(root.left, min, mid)+query(root.right, mid+1, max);
        }
    }
}

相关文章

  • 基础九 线段树Segment Tree

    线段树功能： O(logN) 找到某区间的 最大最小值 元素个数 区间和 O(1) 得到全部区间的 最大最小值 元...

  • 线段树(Segment Tree)

    线段树本质上还是二叉树, 不同的是它的每个节点记录了一段区间的信息.所以很多算法的实现还是大量的递归, 二分的思路...

  • Segment Tree线段树

    线段树的作用范围：区间单点更新和覆盖，区间多点更新和覆盖。时间复杂度：O（logN）原理图： 对于一个长度为N的数...

  • 线段树（segment tree），看这一篇就够了

    定义 线段树（segment tree），顾名思义， 是用来存放给定区间（segment, or interval...

  • 10.线段树(比较高级的数据结构)

    一、线段树(区间树)的概念 Segment Tree;线段树属于高级数据结构，经常出现在算法竞赛中为什么要使用线段...

  • 数据结构之线段树

    什么是线段树 线段树（Segment Tree）也叫区间树，其本质上是一种二分搜索树[https://www.ji...

  • 9-玩转数据结构-线段树

    上一章我们介绍了堆，这一章我们介绍一种新的树结构，线段树(区间树) Segment Tree 为什么使用线段树？ ...

  • Data Structure_树

    线段树Segment Tree 对于有一类问题，时常关注的是一个区间或者是一个线段，那么就可以使用线段树来解决。比...

  • 数据结构之线段树及其应用

    线段树Segment Tree 线段树作为一种高级数据结构主要解决的是和区间有关的问题，当我们关注的问题为区间的某...

  • Segment Tree 线段树 原理及实现

    关于我的 Leetcode 题目解答，代码前往 Github：https://github.com/chenxia...

网友评论

    本文标题：基础九 线段树Segment Tree

    本文链接：https://www.haomeiwen.com/subject/zgjohqtx.html

    延伸阅读

    深度阅读

    • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

    栏目导航

    热点阅读

    线段树

    关于我们|服务条款|联系我们|基础九 线段树Segment Tree|投稿指南|网站地图|RSS订阅|排版工具|手机版

    提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

    Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

    备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

    本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

    所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！