Java数据结构之线段树中的懒操作详解

什么是线段树

线段树是一种常用的数据结构，用于快速解决区间查询类问题。 线段树可以支持区间修改，单点查询，区间查询等操作。

线段树是采用二叉树的结构形成的，一个节点表示一个区间[left, right]。每个节点包含三个值：节点对应的区间范围[left, right]、节点代表的值val、以及节点所拥有的标记，通常标记用来记录区间修改的信息，也称为懒标记。

线段树中的懒操作

线段树自上而下递归下去，如果遇到一个节点的区间完全包含查询区间，则直接返回节点上的值，否则就分别递归该节点的左儿子和右儿子进行查询。 我们每次递归到一个节点时，都需要将该节点的lazy标记下传到其左右子节点。 为了避免重复下传标记，当节点被标记之后，我们将懒标记暂存，到下次对区间取值或区间修改时再进行下传，这样可以使得标记下传的复杂度为O(logn)。

线段树中主要涉及到以下两种类型的操作：

区间修改

区间修改操作是在指定区间内增加或修改某个值。当需要修改某个区间的值时，我们可以标记该区间需要被修改，而对于该区间的子节点，我们将修改信息暂时存储到懒标记中，等到子节点被查询到时，才下推修改。

这个过程比较简单，如果我们需要将区间[l, r]内的值都增加c，我们只需要将该区间对应节点的val值增加c即可，同时要将这个修改操作保存到懒标记中，让其下传到子节点。具体代码如下：

void update(int rt, int l, int r, int L, int R, int val) {  // rt 表示当前节点的编号，表示区间[l, r]。l, r 表示节点表示的区间范围。L, R 表示需要修改的区间。
    if(l >= L and r <= R) {
        tr[rt] += val * (r - l + 1);
        lazy[rt] += val;
        return;
    }
    pushdown(rt, r - l + 1);
    int mid = (l + r) >> 1;
    if(L <= mid) update(rt << 1, l, mid, L, R, val);
    if(R > mid) update(rt << 1 | 1, mid + 1, r, L, R, val);
    pushup(rt);
}

区间查询

区间查询即为查找某个区间[l, r]内的值，该操作比较简单，如果当前查询的区间[l, r]与当前节点表示的区间有重合，则需要向下递归查询其左右子节点，具体代码如下：

int query(int rt, int l, int r, int L, int R) { // rt 表示当前节点的编号，表示区间[l, r]
    if(l >= L and r <= R) {
        return tr[rt];
    }
    pushdown(rt, r - l + 1);
    int mid = (l + r) >> 1;
    int res = 0;
    if(L <= mid) res += query(rt << 1, l, mid, L, R);
    if(R > mid) res += query(rt << 1 | 1, mid + 1, r, L, R);
    return res;
}

示例说明：

以下是一个建立线段树，并进行区间修改和区间查询的示例代码：

import java.util.Arrays;

public class SegmentTree {

    private int[] tr;
    private int[] lazy;

    public SegmentTree(int n) { 
        tr = new int[n << 2];
        lazy = new int[n << 2];
        Arrays.fill(lazy, 0); // 初始化时，所有节点的懒标记都为0
    }

    private void pushup(int rt) {
        tr[rt] = tr[rt << 1] + tr[rt << 1 | 1];  // 更新父节点的值
    }

    private void pushdown(int rt, int len) {
        if(lazy[rt] != 0) {
            lazy[rt << 1] += lazy[rt];
            lazy[rt << 1 | 1] += lazy[rt];
            tr[rt << 1] += lazy[rt] * (len - (len >> 1));
            tr[rt << 1 | 1] += lazy[rt] * (len >> 1);
            lazy[rt] = 0;
        }
    }

    public void update(int rt, int l, int r, int L, int R, int val) {
        if(l >= L && r <= R) {
            tr[rt] += val * (r - l + 1);
            lazy[rt] += val;
            return;
        }
        pushdown(rt, r - l + 1);
        int mid = (l + r) >> 1;
        if(L <= mid) update(rt << 1, l, mid, L, R, val);
        if(R > mid) update(rt << 1 | 1, mid + 1, r, L, R, val);
        pushup(rt);
    }

    public int query(int rt, int l, int r, int L, int R) {
        if(l >= L && r <= R) {
            return tr[rt];
        }
        pushdown(rt, r - l + 1);
        int mid = (l + r) >> 1;
        int res = 0;
        if(L <= mid) res += query(rt << 1, l, mid, L, R);
        if(R > mid) res += query(rt << 1 | 1, mid + 1, r, L, R);
        return res;
    }

    public static void main(String[] args) {

        int[] nums = {1, 3, 5, 7, 8, 9};
        SegmentTree st = new SegmentTree(nums.length);
        buildTree(1, 0, nums.length - 1, nums, st);

        // 对[0,2]区间进行加10操作
        st.update(1, 0, nums.length - 1, 0, 2, 10);
        System.out.println(st.query(1, 0, nums.length - 1, 0, 2)); // 输出：36

        // 对[3,5]区间进行加5操作
        st.update(1, 0, nums.length - 1, 3, 5, 5);
        System.out.println(st.query(1, 0, nums.length - 1, 3, 5)); // 输出：22
    }

    private static void buildTree(int rt, int l, int r, int[] nums, SegmentTree st) {
        if(l == r) {
            st.tr[rt] = nums[l];
        } else {
            int mid = (l + r) >> 1;
            buildTree(rt << 1, l, mid, nums, st);
            buildTree(rt << 1 | 1, mid + 1, r, nums, st);
            st.pushup(rt);
        }
    }
}

该示例代码建立了一个线段树，并对[0,2]区间进行加10操作后，进行区间查询，输出结果为36。然后再对区间[3,5]进行加5操作，进行区间查询，输出结果为22。

以上就是Java数据结构之线段树中的懒操作详解的完整攻略。