Java数据结构之线段树的原理与实现

什么是线段树

线段树是一种基于分治思想的数据结构，它可以用来解决各种区间查询问题，例如区间求和、最大值、最小值等等。在算法竞赛和数据结构课程中，线段树被广泛应用，是一种非常实用的数据结构。

线段树的基本原理

线段树是一种二叉树，它的每个节点包含一个区间，叶子节点表示区间中的单个元素，非叶子节点表示区间的合并。

线段树的建立过程分为三步：

1. 从上到下递归地将区间划分为两个子区间。
2. 当划分到区间长度为1时，将该节点标记为叶子节点，将该位置对应的数值存入该叶子节点。
3. 从下到上递归地合并每个节点的信息。例如求和的话，每个节点需要记录一个区间的和。

查询的过程也分为三步：

1. 先找到包含查询区间的最小区间。
2. 对于覆盖完全的区间，直接返回该区间的信息，否则，递归地查询该节点的子节点。
3. 将子节点的信息合并，得到查询区间的结果。

修改操作则是找到该位置对应的叶子节点，然后递归地重新合并所有受到该修改操作影响的节点的信息。

编程实现

我们可以使用Java来实现线段树的建立和查询操作。下面是一个示例代码：

class SegmentTree {
    int n;
    int[] nums;
    int[] tree;

    public SegmentTree(int[] nums) {
        this.n = nums.length;
        this.nums = nums;
        this.tree = new int[n * 4];
        build(0, 0, n - 1);
    }

    private void build(int node, int left, int right) {
        if (left == right) {
            tree[node] = nums[left];
        } else {
            int mid = left + (right - left) / 2;
            build(node * 2 + 1, left, mid);
            build(node * 2 + 2, mid + 1, right);
            tree[node] = tree[node * 2 + 1] + tree[node * 2 + 2];
        }
    }

    public int query(int left, int right) {
        return query(0, 0, n - 1, left, right);
    }

    private int query(int node, int nodeLeft, int nodeRight, int queryLeft, int queryRight) {
        if (nodeLeft >= queryLeft && nodeRight <= queryRight) {
            return tree[node];
        } else if (nodeRight < queryLeft || nodeLeft > queryRight) {
            return 0;
        } else {
            int mid = nodeLeft + (nodeRight - nodeLeft) / 2;
            return query(node * 2 + 1, nodeLeft, mid, queryLeft, queryRight)
                    + query(node * 2 + 2, mid + 1, nodeRight, queryLeft, queryRight);
        }
    }

    public void update(int index, int val) {
        update(0, 0, n - 1, index, val);
    }

    private void update(int node, int nodeLeft, int nodeRight, int index, int val) {
        if (nodeLeft == nodeRight) {
            tree[node] = val;
        } else {
            int mid = nodeLeft + (nodeRight - nodeLeft) / 2;
            if (index <= mid) {
                update(node * 2 + 1, nodeLeft, mid, index, val);
            } else {
                update(node * 2 + 2, mid + 1, nodeRight, index, val);
            }
            tree[node] = tree[node * 2 + 1] + tree[node * 2 + 2];
        }
    }
}

上面的代码实现了线段树的基本功能，包括建树、查询和修改。可以根据实际需求对其进行更改。

示例说明1：使用线段树查询数组的区间和

下面是一个使用线段树查询数组的区间和的示例代码：

public class Main {
    public static void main(String[] args) {
        int[] nums = {1, 3, 5, 7, 9, 11};
        SegmentTree tree = new SegmentTree(nums);
        System.out.println(tree.query(0, 2)); // 1 + 3 + 5 = 9
        tree.update(1, 2);
        System.out.println(tree.query(0, 2)); // 1 + 2 + 5 = 8
    }
}

该示例中，我们将数组 {1, 3, 5, 7, 9, 11} 转化为线段树，并查询区间 [0, 2] 的和。然后我们将该数组的第二个元素修改为2，之后再次查询区间 [0, 2] 的和。控制台将输出9和8。

示例说明2：使用线段树查询数组的区间最大值

下面的示例代码演示了如何使用线段树查询数组的区间最大值：

public class Main {
    static class Node {
        int val;
        int start, end;

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

    public static void main(String[] args) {
        int[] nums = {1, 3, 5, 2, 4, 6, 8};
        List<Node> list = new ArrayList<>(nums.length);
        for (int i = 0; i < nums.length; i++) {
            Node node = new Node(nums[i], i, i);
            list.add(node);
        }

        SegmentTree tree = new SegmentTree(list.stream().mapToInt(n -> n.val).toArray());

        IntStream.range(0, nums.length - 1).forEach(i -> {
            Node left = list.get(i);
            Node right = list.get(i + 1);
            if (left.val > right.val) {
                left.end = right.start;
            }
        });

        int ans = 0;
        for (Node node : list) {
            ans = Math.max(ans, tree.query(node.start, node.end));
        }

        System.out.println(ans);
    }
}

该示例中，我们将数组 {1, 3, 5, 2, 4, 6, 8} 转化为线段树，并查询其中的区间最大值。我们还通过修改线段树节点信息来查找每个局部最大值的起始和结束位置。控制台将输出 6，表示数组中的最大值为6。

总结

线段树是一种实用而优秀的数据结构，它可以用来解决区间问题。建树、查询和修改等操作都能快速实现，并且时间复杂度为 O(log n)。在算法竞赛和数据结构课程中，掌握线段树的原理和实现是必不可少的。