Java資料結構之線段樹中的懶操作詳解

package com.platform.modules.alg.alglib.p85;
 
public class P85 {
    public String output = "";
 
    private final int maxn = 100005;
    private final int inf = 0x3f3f3f3f;
    private int n;
    private int a[] = new int[maxn];
    private node tree[] = new node[maxn * 4]; // 樹結點儲存陣列
 
    public P85() {
        for (int i = 0; i < tree.length; i++) {
            tree[i] = new node();
        }
    }
 
    void lazy(int k, int v) {
        tree[k].mx = v; // 更新最值
        tree[k].lz = v; // 做懶標記
    }
 
    // 向下傳遞懶標記
    void pushdown(int k) {
        lazy(2 * k, tree[k].lz); // 傳遞給左孩子
        lazy(2 * k + 1, tree[k].lz); // 傳遞給右孩子
        tree[k].lz = -1; // 清除自己的懶標記
    }
 
    // 建立線段樹,k表示儲存下標,區間[l,r]
    void build(int k, int l, int r) {
        tree[k].l = l;
        tree[k].r = r;
        tree[k].lz = -1; // 初始化懶操作
        if (l == r) {
            tree[k].mx = a[l];
            return;
        }
        int mid, lc, rc;
        mid = (l + r) / 2; // 劃分點
        lc = k * 2; // 左孩子儲存下標
        rc = k * 2 + 1; // 右孩子儲存下標
        build(lc, l, mid);
        build(rc, mid + 1, r);
        tree[k].mx = Math.max(tree[lc].mx, tree[rc].mx); // 結點的最大值等於左右孩子最值的最大值
    }
 
    // 將區間 [l，r] 修改更新為 v
    void update(int k, int l, int r, int v) {
        // 找到該區間
        if (tree[k].l >= l && tree[k].r <= r) {
            lazy(k, v); // 更新並做懶標記
            return;
        }
        if (tree[k].lz != -1)
            pushdown(k); // 懶標記下移
        int mid, lc, rc;
        mid = (tree[k].l + tree[k].r) / 2; // 劃分點
        lc = k * 2; // 左孩子儲存下標
        rc = k * 2 + 1; // 右孩子儲存下標
        if (l <= mid)
            update(lc, l, r, v); // 到左子樹更新
        if (r > mid)
            update(rc, l, r, v);// 到右子樹更新
        tree[k].mx = Math.max(tree[lc].mx, tree[rc].mx); // 返回時修改更新最值
    }
 
    // 求區間 [l，r] 的最值
    int query(int k, int l, int r) {
        int Max = -inf;
        if (tree[k].l >= l && tree[k].r <= r) // 找到該區間
            return tree[k].mx;
        if (tree[k].lz != -1)
            pushdown(k); // 懶標記下移
        int mid, lc, rc;
        mid = (tree[k].l + tree[k].r) / 2; // 劃分點
        lc = k * 2; // 左孩子儲存下標
        rc = k * 2 + 1; // 右孩子儲存下標
        if (l <= mid)
            Max = Math.max(Max, query(lc, l, r)); // 到左子樹查詢
        if (r > mid)
            Max = Math.max(Max, query(rc, l, r)); // 到右子樹查詢
        return Max;
    }
 
    public String cal(String input) {
        int l, r;
        int i, v;
        String[] line = input.split("n");
        n = Integer.parseInt(line[0]); // 第 1 行：10
        String[] nums = line[1].split(" ");
 
 
        // 第 2 行：5 3 7 2 12 1 6 4 8 15
        for (i = 1; i <= n; i++)
            a[i] = Integer.parseInt(nums[i - 1]);
        build(1, 1, n); // 建立線段樹
        // 輸入查詢最值的區間 [l，r] 1 10
        String[] range = line[2].split(" ");
        l = Integer.parseInt(range[0]);
        r = Integer.parseInt(range[1]);
        // 求區間[l..r]的最值
        output += query(1, l, r) + "n";
        // 輸入更新的區間值 l r v  第 3 行： 3 7 25
        String[] change = line[3].split(" ");
        l = Integer.parseInt(change[0]);
        r = Integer.parseInt(change[1]);
        v = Integer.parseInt(change[2]);
        // 將區間 [l，r] 修改更新為 v
        update(1, l, r, v);
        // 求區間[l..r]的最值 第 4 行：1 10
        range = line[4].split(" ");
        l = Integer.parseInt(range[0]);
        r = Integer.parseInt(range[1]);
        // 求區間 [l..r] 的最值
        output += query(1, l, r) + "n";
        return output;
    }
}
 
// 結點
class node {
    int l; // l 表示區間左右端點
    int r; // r 表示區間左右端點
    int mx; // mx表示區間[l,r]的最值
    int lz; // lz 懶標記
}