线段树

线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。

线段树可以在 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。

线段树维护的信息，需要满足可加性，即能以可以接受的速度合并信息和修改信息，包括在使用懒惰标记时，标记也要满足可加性（例如取模就不满足可加性，对 取模然后对 取模，两个操作就不能合并在一起做）。

1.区间求和的线段树

若只需要求区间和，而不需要改变区间值 —> 使用前缀和

若在求区间和的基础上，还要修改区间数组的值，为了更快的维护一个前缀和数组 —-> 线段树

线段树实际就是在前缀和的基础上使用二分构建二叉搜索树，提高修改区间值的时间

线段树一般支持三个基本操作：构建树，修改某元素的值，查询区间和

如图：原数组和它对应的线段树

修改下标为4的元素为6后的线段树：

一个区间求和线段树的Java基本模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
public class SegmentTree {
    private int[] data;   // 原始数据
    private int[] tree;   // 线段树

    public SegmentTree(int[] data) {
        this.data = data;
        tree = new int[data.length*4];     // 线段树为原始数据4倍
        buildTree(0,0,data.length-1);
    }

    // 构建树
    private void buildTree(int treeIndex, int l, int r){
        if(l == r){
            tree[treeIndex] = data[l];
            return;
        }
        int leftTreeIndex = 2 * treeIndex + 1;
        int rightTreeIndex = 2 * treeIndex + 2;
        int mid = (l+r)/2;
        buildTree(leftTreeIndex, l, mid); //先构建两棵子树
        buildTree(rightTreeIndex, mid + 1, r);
        tree[treeIndex] = tree[leftTreeIndex] + tree[rightTreeIndex];
    }

    // 更新下标为index的值为val
    public void update(int treeIndex, int l, int r,int index,int val){
        if(l == r){
            data[index] = val;
            tree[treeIndex] = val;
            return;
        }
        int mid = (l+r)/2;
        int leftTreeIndex = 2 * treeIndex + 1;
        int rightTreeIndex = 2 * treeIndex + 2;
        if(index >= l && index <= mid){
            update(leftTreeIndex, l, mid,index,val);
        } else{
            update(rightTreeIndex, mid+1, r,index,val);
        }
        // 自底往上更新线段树
        tree[treeIndex] = tree[leftTreeIndex] + tree[rightTreeIndex];
    }

    // 查询 L-R 区域的值的和
    public int query(int treeIndex, int l, int r,int queryL,int queryR){
        System.out.println(l + " " + r);
        if(queryR < l || queryL > r) return 0;
        else if(queryL <= l && r <= queryR) return tree[treeIndex];
        else {
            int mid = l + (r - l) / 2;
            int leftTreeIndex = 2 * treeIndex + 1;
            int rightTreeIndex = 2 * treeIndex + 2;
            int sum_left =  query(leftTreeIndex, l, mid, queryL, queryR);
            int sum_right = query(rightTreeIndex, mid + 1, r, queryL, queryR);
            return sum_left + sum_right;
        }
    }

}

若要使用更复杂的数据结构和运算规则，修改：

1
2
3
4
private int[] data;   // 原始数据
private int[] tree;   // 线段树
和
 tree[treeIndex] = tree[leftTreeIndex] + tree[rightTreeIndex];		// 此处在进行区间求和

参考资料：
灯笼大神讲线段树

线段树百科