前言

在刷题过程中，经常会遇到求数组某区间之和的问题：给出数组a[0...n-1]，求数组下标i~j的元素之和a[i]+...+a[j]，0<=i<=j<n。
纯暴力做法是O(n)，即把区间的数加起来。
好一点办法的是创建一个前缀和（prefix sum）数组p，使得p[i]=a[0]+...+a[i]，那么所求结果就是p[j]-p[i-1]，当然i=0需要特别处理一下。这样准备工作是O(n)，查询只需要O(1)。
一般来说，数组不变的情况下方法二已经够用了。但是当数组有可能改变的时候，每次改变都需要更新前缀和数组，效率不高。
好在，有专门的数据结构来满足这种操作需求。今天我们就来简单学习一下线段树（Segment Tree）和树状数组（Fenwick Tree）。

线段树

顾名思义，线段树是树。具体一点，二叉树。那么“线段”二字如何体现？是把i-j区间之和想象成i-j的线段（我瞎猜的）。简而言之，线段树就是把区间之和用树来显示。
很自然地，根是整个数组区间，然后左右分半，依次类推。奇数情况下是左边多还是右边多呢？其实都可以，不过考虑区间[a,b]，最自然的写法可分为[a,(a+b)/2]与[(a+b)/2,b]，当b-a是奇数时右边多，这样写起来更自然方便些。
从网上搜了个图，这样更直观：

image.png

怎么构造这棵树呢？
首先要决定树的节点。左右子节点等属性是很自然的。同时需要存储表示的区间，以及区间之和。
需不需要指针指向parent节点呢？大可不必。
至于重要的几个操作，构造，查询，更新，抓住递归的特点，自下而上地进行，一切都显得自然了。
构造：递归，先构造左右，再构造自己，这样其实是从底层往上构造。
查询：同样递归，假如查询的区间就是自己马上返回，否则就有三种情况：查询左边，查询右边，两边都有。
更新：和查询类似，不同的是一次只更新一个元素，所以只会走一边。路径相当于查询[i,i]，下到最底层更新值。注意路径之上的节点也要跟着更新和。
当然了，start和end在这里是inclusive的，和java传统惯例有点不一样，但是这系列的习惯好像就这样，毕竟要表示单个元素。树的高度是O(logn)，而查询操作近似遍历树，所以也是O(logn)。更新操作类似，同样是O(logn)。构造的话，要把节点都过一遍，所以是O(n)。代码如下：

class SegmentTree {

    private static class TreeNode {
        int start, end, sum;
        TreeNode left, right;

        TreeNode(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    private TreeNode buildTree(int[] nums, int start, int end) {
        if (start > end) return null;
        TreeNode cur = new TreeNode(start, end);
        if (start == end) cur.sum = nums[start];
        else {
            int mid = start + (end - start) / 2;
            cur.left = buildTree(nums, start, mid);
            cur.right = buildTree(nums, mid + 1, end);
            cur.sum = cur.left.sum + cur.right.sum;
        }
        return cur;
    }

    private void updateTree(TreeNode node, int i, int val) {
        if (node.start == node.end) {
            node.sum = val;
        } else {
            int mid = node.start + (node.end - node.start) / 2;
            if (i <= mid) updateTree(node.left, i, val);
            else updateTree(node.right, i, val);
            node.sum = node.left.sum + node.right.sum;
        }
    }

    private int queryTree(TreeNode node, int i, int j) {
        if (node.start == i && node.end == j) return node.sum;
        else {
            int mid = node.start + (node.end - node.start) / 2;
            if (j <= mid) {
                return queryTree(node.left, i, j);
            } else if (i >= (mid + 1)) {
                return queryTree(node.right, i, j);
            } else {
                return queryTree(node.left, i, mid) + queryTree(node.right, mid + 1, j);
            }
        }
    }

    private TreeNode root;

    SegmentTree(int[] nums) {
        root = buildTree(nums, 0, nums.length - 1);
    }

    public void update(int i, int val) {
        updateTree(root, i, val);
    }

    public int sumRange(int i, int j) {
        return queryTree(root, i, j);
    }
}

代码量还是不小的，毕竟用了树。

树状数组

树状数组（也叫Binary Indexed Tree）就是指用数组来表示一棵树，这样空间上更节约。类似的还有binary heap。
那么树怎么放进数组呢？根据维基百科，对于数组里的下标i进行一个特定的位运算，就可以获得其父节点所在的下标。听起来很神奇？刚开始我也不知所云，直到看了Competitive Programming Algorithms的解释：

image.png

image.png

class BinaryIndexedTree {

    private final int[] BITree, arr;

    public BinaryIndexedTree(int[] arr) {
        this.arr = arr;
        BITree = new int[arr.length + 1];
        for (int i = 0; i < arr.length; i++) updateBIT(i, arr[i]);
    }

    public int sumRange(int i, int j) {
        return getSum(j) - getSum(i - 1);
    }

    public void update(int i, int val) {
        int delta = val - arr[i];
        arr[i] = val;
        updateBIT(i, delta);
    }

    private void updateBIT(int index, int delta) {
        index++;
        while (index < BITree.length) {
            BITree[index] += delta;
            index += index & (-index);
        }
    }

    private int getSum(int index) {
        int sum = 0;
        index++;
        while (index > 0) {
            sum += BITree[index];
            index -= index & (-index);
        }
        return sum;
    }
}

可见，其实树状数组并不是简单地把线段树装进数组，而是有另一套计算方法，差别还是挺明显的。
相比之下，树状数组代码量更少，更高效，一般来说是更好的选择。

例题

Range Sum Query - Mutable - LeetCode
以上两种实现改个名字就可以直接当答案了。