数据结构-线段树

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Node {
    int val;
    Node left, right;

    public Node() {}

    public Node(int val) {
        this.val = val;
    }
}

1
2
3
4

void buildTree(Node node, int start, int end) {
    //
    
}

 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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

class SegmentTree {
    private int[] tree; // 维护区间
    private int[] lazy; // 惰性标记，维护修改值

    public SegmentTree(int[] nums) {
        int n = nums.length;
        // 线断树有 n 个叶结点，总结点个数设为 x
        // 非叶结点都有 2 棵子树，则
        // x - 1 = (x - n) * 2
        // x = 2 * n - 1
        // 根结点索引从 1 开始
        tree = new int[n * 2];
        lazy = new int[n * 2];
        build(nums, 0, nums.length - 1, 1);
    }

    void build(int[] nums, int left, int right, int root) {
        // 对 [left, right] 区间建立线段树,当前根的编号为 root
        if (left == right) {
            // 叶结点
            tree[root] = nums[left];
            return;
        }
        // + 优先级高于 >>
        int mid = left + ((right - left) >> 1);
        build(nums, left, mid, root << 1);          // root * 2
        // << 优先级高于 |
        build(nums, mid + 1, right, root << 1 | 1); // root * 2 + 1
        // 子树信息更新父结点信息
        tree[root] = tree[root << 1] + tree[root << 1 | 1];
    }

    int rangeSum(int qLeft, int qRight, int left, int right, int root) {
        // 查询区间 [qLeft, qRight] 的元素总和
        if (qLeft <= left && right <= qRight) {
            // 当前区间是查询区间的子区间
            return tree[root];
        }
        pushDown(left, right, root);
        int mid = left + ((right - left) >> 1);
        int sum = 0;
        if (qLeft <= mid) {
            sum += rangeSum(qLeft, qRight, left, mid, root << 1);
        }
        if (mid < qRight) {
            sum += rangeSum(qLeft, qRight, mid + 1, right, root << 1 | 1);
        }
        return sum;
    }

    void update(int qLeft, int qRight, int val, int left, int right, int root) {
        // 将区间 [qLeft, qRight] 内的元素加 val
        if (qLeft <= left && right <= qRight) {
            tree[root] += val * (right - left + 1);
            // 不必此时修改到叶结点，将修改值记录到父结点的 lazy 标记
            // 下次查询到需要修改的叶结点时再修改
            lazy[root] += val;
            return;
        }
        pushDown(left, right, root);
        int mid = left + ((right - left) >> 1);
        if (qLeft <= mid) {
            update(qLeft, qRight, val, left, mid, root << 1);
        }
        if (mid < qRight) {
            update(qLeft, qRight, val, mid + 1, right, root << 1 | 1);
        }
        tree[root] = tree[root << 1] + tree[root << 1 | 1];
    }

    private void pushDown(int left, int right, int root) {
        // lazy 标记处理
        int mid = left + ((right - left) >> 1);
        if (lazy[root] > 0 && left < right) {
            // 如果当前节点的 lazy 标记非空，则更新当前节点两个子节点的值和 lazy 标记
            tree[root << 1] += lazy[root] * (mid - left + 1);
            tree[root << 1 | 1] += lazy[root] * (right - mid);
            lazy[root << 1] += lazy[root];
            lazy[root << 1 | 1] += lazy[root];
            lazy[root] = 0;
        }
    }
}