线段树

介绍

线段树是一棵二叉树，他的每个结点包含了两个额外的属性 start 和 end 用于表示该结点所代表的区间。start 和 end 都是整数，并按照如下的方式赋值:

根结点的 start 和 end 由 build 方法所给出。
对于结点 A 的左儿子，有 start=A.start, end=(A.start + A.end) / 2。
对于结点 A 的右儿子，有 start=(A.start + A.end) / 2 + 1, end=A.end。
如果 start 等于 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


class Node:
    def __init__(self, start, end, max):
        self.start, self.end, self.max = start, end, max
        self.left, self.right = None, None


def build(A, start, end):
    if start > end: return None
    root = Node(start, end, A[start])
    if start == end: return root
    mid = (start + end) // 2
    root.left = build(A, start, mid)
    root.right = build(A, mid + 1, end)
    root.max = max(root.left.max, root.right.max)
    return root


def query(root, start, end):
    if start == root.start and end == root.end: return root.max
    mid = (root.start + root.end) // 2
    if end <= mid: return query(root.left, start, end)
    if start > mid: return query(root.right, start, end)
    return max(query(root.left, start, mid), query(root.right, mid + 1, end))


def update(root, index, value):
    if root.start == root.end == index:
        root.max = value
        return

    mid = (root.start + root.end) // 2
    if index <= mid: update(root.left, index, value)
    else: update(root.right, index, value)
    root.max = max(root.left.max, root.right.max)

 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


struct Node{
    int start, end, max;
    Node *left, *right;
    Node (int start, int end, int max) : start(start), end(end), max(max), left(nullptr), right(nullptr) {};
};

Node* build(vector<int> &A, int start, int end) {
    if (start > end) return nullptr;
    auto root = new Node(start, end, A[start]);
    if (start == end) return root;
    int mid = start + ((end - start) >> 1);
    root->left = build(A, start, mid);
    root->right = build(A, mid + 1, end);
    root->max = max(root->left->max, root->right->max);
    return root;
}

int query(Node *root, int start, int end) {
    if (start == root->start && end == root->end) return root->max;
    int mid = root->start + ((root->end - root->start) >> 1);
    if (end <= mid) return query(root->left, start, end);
    else if (start > mid) return query(root->right, start, end);
    return max(query(root->left, start, mid), query(root->right, mid + 1, end));
}

void update(Node *root, int index, int val) {
    if (root->start == root->end && root->start == index) {
        root->max = val;
        return ;
    }
    int mid = root->start + ((root->end - root->start) >> 1);
    if (index <= mid) update(root->left, index, val);
    else update(root->right, index, val);
    root->max = max(root->left->max, root->right->max);
}

例题