基础九线段树Segment Tree

线段树功能：

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);
        }
    }
}

最后编辑于：2018.12.18 06:41:47

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 216,287评论 6赞 498
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 92,346评论 3赞 392
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 162,277评论 0赞 353
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,132评论 1赞 292
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,147评论 6赞 388
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,106评论 1赞 295
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,019评论 3赞 417
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,862评论 0赞 274
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,301评论 1赞 310
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,521评论 2赞 332
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,682评论 1赞 348
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,405评论 5赞 343
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,996评论 3赞 325
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,651评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,803评论 1赞 268
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,674评论 2赞 368
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,563评论 2赞 352

基础九 线段树Segment Tree

lt439 Segment Tree Build II + lt202 Segment Tree Query

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

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

lt249 Count of Smaller Number before itself

315 Count of Smaller Numbers After Self

lt248 Count of Smaller Number

推荐阅读更多精彩内容

基础九线段树Segment Tree

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

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