数据结构：线段树（SegNode）

作用

对于区间的修改和查询的时间复杂度都是log级别的，比如计算一个区间的和

线段树的定义

它其实就是一颗二叉树，

• 但它有一个范围left,right
• 左子树的范围是 left - center，右子树的范围是 center - right
• 而当前count = lChild.count + rChild.count
• 而叶子节点的左右范围是一样的，也就是叶子节点只有一个值，而不是一个范围

public class SegNode {
    int left,right,count;
    SegNode lChild,rChild;

    public SegNode(int left, int right) {
        this.left = left;
        this.right = right;
        this.count = 0;
    }
}
1
2
3
4
5
6
7
8
9
10

如何管理线段树

此时，我们可以定义一个管理类来管理线段树

• build： 构建一个线段树
• count：计算这个范围内的数量的和
• insert：在这个范围内插入一个元素

public class SegNodeManager {

    public static SegNode build(int left,int right){
        SegNode ret = new SegNode(left,right);
        if(left == right){
            return ret;
        }
        int center = (left + right) / 2;
        ret.lChild = build(left,center);
        ret.rChild = build(center + 1,right);
        return ret;
    }

    /*
        只有当传进来的范围大于root，才返回root的值
        1. 如果传入的范围和 root互补覆盖，则直接返回0
        2. 否则在还在中找 left + right的范围
     */
    public static int count(SegNode root,int left,int right){
        if(left > root.right || right < root.left){ // 互补相关
            return 0;
        }
        if(left <= root.left  && right >= root.right){
            return root.count;
        }
        return count(root.lChild,left,right) + count(root.rChild,left,right);
    }

    /*
        val：增长的对象
     */
    public static void insert(SegNode root,int val){
        root.count++;
        if(root.left == root.right){
            return;
        }
        int center = (root.left + root.right)/2;
        if(val <= center){
            insert(root.lChild,val);
        } else {
            insert(root.rChild,val);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

缺点

如果范围特别大怎么办？

1. 方式一：可以利用map，将可能出现的范围，映射到部分值中
2. 方式二：构建线段树的时候，延迟初始化没有用上的范围

方式二的例子

class SegNodeManager01{

    /*
        这里需要传入root的最大值和最小值，并将root返回
     */
    public static SegNode build(long left,long right){
        SegNode root = new SegNode(left,right);
        return root;
    }

    /*
        计算left 到 right之间有多少数
        1. 如果root为空，就返回0
        2. 如果root和left、right没有任何交集，也返回0
        3. 如果前部覆盖，则返回当前值
        否则返回2个孩子
     */
    public static int count(SegNode root,long left,long right){
        if(root == null){
            return 0;
        }
        if(left > root.right || right < root.left){
            return 0;
        }
        if(left <= root.left && right >= root.right){
            return root.count;
        }
        return count(root.lChild,left,right) + count(root.rChild,left,right);
    }

    /*
        插入元素
     */
    public static void insert(SegNode root,long value){
        root.count++;
        if(root.left == root.right){ // 结束了
            return;
        }
        long center = root.left + (root.right - root.left)/2; // 注意这里，是防止负数时，进入死循环
        if(value <= center){
            if(root.lChild == null){
                root.lChild = new SegNode(root.left,center);
            }
            SegNode left = root.lChild;
            insert(left,value);
        } else {
            if(root.rChild == null){
                root.rChild = new SegNode(center + 1 ,root.right);
            }
            SegNode right = root.rChild;
            insert(right,value);
        }
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55