线段树

概述

线段树，也叫区间树，是一个完全二叉树，它在各个节点保存一条线段（即“子数组”），因而常用于解决数列维护问题，它基本能保证每个操作的复杂度为O(lgN)。

特点

1、线段树是一棵高度平衡的二叉树，通常为完全二叉树（叶子节点不一定在同一层，但可以通过将最后一层非叶子节点的值视为null进行构造）

2、线段树的每一个结点都代表一个区间。父结点所代表的区间是两个子结点的和（或者其他操作，可以自己定义）。兄弟结点所代表的区间相互不重叠。根结点代表整个区间

实现思路

线段树是一种基于分治算法的二叉树。每个结点维护一个区间，以及在该区间内的数据信息。在当前结点，它的区间是[left,right]，则它的两个子结点的区间分别为[left, mid]，[mid+1, right]。由于采用了分治的思想，在进行操作时每一层至多访问两个结点，极大优化了效率。

同时，根据完全二叉树的规律，如果原始数组有n个元素，则要使用数组对线段树进行存储的话，需要4n的空间。

主要方法

1、构造线段树

2、区间查询

3、区间修改

实现

基本实现

1、构造用于定义线段树计算方法的接口

public interface Merger<E> {
    E merge(E a, E b);
}

2、线段树类的基本实现

public class SegmentTree<E> {

    private E[] tree;	// 存储线段树
    private E[] data;	// 存储原始数据
    private Merger<E> merger;	// 定义线段树计算方法

    public SegmentTree(E[] arr, Merger<E> merger) {

        this.merger = merger;

        data = (E[])new Object[arr.length];
        for (int i = 0; i< arr.length; i++) {
            data[i] = arr[i];
        }

        tree = (E[])new Object[4 * arr.length];
        buildSegmentTree(0, 0, data.length-1);	// 构造线段树

    }

	// 获取左孩子索引
    private int leftChild(int index) {
        return 2 * index + 1;
    }
	
	// 获取右孩子索引
    private int rightChild(int index) {
        return 2 * index + 2;
    }

}

构造线段树

使用递归构造线段树，整个过程有点像使用一个有序数组构造二叉搜索树。

private void buildSegmentTree(int treeIndex, int l, int r) {
    if(l == r) {
        tree[treeIndex] = data[l];
        return;
    }
    int leftTreeIndex = leftChild(treeIndex);
    int rightTreeIndex = rightChild(treeIndex);
    int mid = l + (r - l) / 2;
    buildSegmentTree(leftTreeIndex, l, mid);
    buildSegmentTree(rightTreeIndex, mid+1, r);
    tree[treeIndex] = merger.merge(tree[leftTreeIndex], tree[rightTreeIndex]);
}

区间查询

也是使用递归进行查询，分三种情况进行讨论。

// 返回[queryL, queryR]的值
public E query(int queryL, int queryR) {
    if(queryL < 0 || queryL >= data.length ||
        queryR < 0 || queryR >= data.length || queryL > queryR) {
        throw new IllegalArgumentException("Index is illegal");
    }
    return query(0, 0, data.length-1, queryL, queryR);
}

private E query(int treeIndex, int l, int r, int queryL, int queryR) {
    if(l == queryL && r == queryR) {
        return tree[treeIndex];
    }
    int mid = l+(r-l)/2;
    int leftTreeIndex = leftChild(treeIndex);
    int rightTreeIndex = rightChild(treeIndex);
    if(queryL >= mid + 1) {
        return query(rightTreeIndex, mid+1, r, queryL, queryR);
    }
    else if(queryR <= mid) {
        return query(leftTreeIndex, l, mid, queryL, queryR);
    }
    E leftResult = query(leftTreeIndex, l, mid, queryL, mid);
    E rightResult = query(rightTreeIndex, mid+1, r, mid+1, queryR);
    return merger.merge(leftResult, rightResult);
}

区间修改

// 将index位置的值，更新为e
public void set(int index, E e) {
    if(index < 0 || index >= data.length)
        throw new IllegalArgumentException("Index is illegal");
    data[index] = e;
    set(0, 0, data.length-1, index, e);
}

// 在以treeIndex为根的线段树中更新index的值为e
private void set(int treeIndex, int l, int r, int index, E e) {
    if(l == r) {
        tree[treeIndex] = e;
        return;
    }
    int mid = l + (r-l)/2;
    int leftTreeIndex = leftChild(treeIndex);
    int rightTreeIndex = rightChild(treeIndex);
    if(index >= mid+1)
        set(rightTreeIndex, mid+1, r, index, e);
    else
        set(leftTreeIndex, l, mid, index, e);
    tree[treeIndex] = merger.merge(tree[leftTreeIndex], tree[rightTreeIndex]);
}

Donate