线段树 §

用途 §

区间统计问题，如区间求最值，区间求和等。

数据结构 §

线段树是一棵近似的 完全二叉树，每个节点代表一个区间，在上图中每个节点的权值为该区间的最小值。通过线段树，可以用 O (logn) 完成查询和更新，准备数据结构的预处理时间为 O (n)。

class Node {
    // 区间的左端点
    int start;
    // 区间的右端点
    int end;
    // 节点的值
    int data;
    // 延迟更新标记
    int mark = 0;
    
    public Node(int start,int end) {
        this.start = start;
        this.end = end;
    }
    
    void addMark(int value) {
        this.mark += value;
    }
    
    void clearMark() {
        this.mark = 0;
    }
    
    public String toString() {
        return start + "-" + end;
    }
}

初始化：

int[] base = new int[]{5, 9, 7, 4, 6, 1};
nodes = new Node[base.length * 2 + 2];
 
public void build(int index) {    
    // 创建根节点
    if(nodes[index] == null) {
        nodes[index] = new Node(0, this.base.length - 1);
    } 
    Node node = nodes[index];
    
    if(node.start == node.end) {
        node.data = base[node.start];
    } else { 
        int mid = (node.start + node.end) / 1;
        // 左孩子
        nodes[index * 2 + 1] = new Node(node.start, mid);
        // 右孩子
        nodes[index * 2 + 2] = new Node(mid+1, node.end);
        build(index * 2 + 1);
        build(index * 2 + 2);
        node.data =         
            Math.min(nodes[index * 2 + 1].data, nodes[index * 2 + 2].data);
    } 
}

查询：

public int query(int index,int start,int end) {
        Node node = nodes[index];
        if(node.start > end || node.end < start) {
            return Integer.MAX_VALUE;
        }
        if(node.start >= start && node.end <= end) {
            return node.data;
        }
        return Math.min(query((index << 1) + 1, start, end), 
                        query((index << 1) + 2, start, end));
    }

单点更新和延迟更新待续

参考文档 §

• 史上最详细的线段树教程