简单了解一下 Segment Tree 和 Fenwick Tree（Binary Indexed Tree）

转载请注明出处：http://blog.csdn.net/hjf_huangjinfu/article/details/77834729

先解决一个简单的问题

        考虑一下我们有一个简单问题，有一个数组 data [0 ~ n-1]，长度为n，给定后数组长度不会变化，现在有三个需求：

        1：我们需要查询该数组某一个范围内所有元素的和，比如 sum(i, j)，{0 <= i <= j <= n-1}。

        2：我们可以对数组任意位置的数据进行修改，修改后，任然需要继续满足需求1，也就是范围内的和。

        3：需求1和需求2的操作次数平均起来是相等的，比如100次操作中，有51次操作1，有49次操作2。

        问题链接：https://leetcode.com/problems/range-sum-query-mutable/description/

        方法1，一个常规方法：

        需求1：每次计算范围和，从i到j，对数组做遍历，然后累加，最后返回结果。

        需求2：直接对数组进行按索引修改。

        性能分析：

       时间复杂度：需求1，每次计算都要做一次遍历，那么平均复杂度为 O(n)。需求2，每次按索引对数组进行修改，平均时间复杂度为O(1)。需求3：由于需求1和需求2操作频率相当，所以需求3的平均时间复杂度为O(n)。

        空间复杂度：只需要一个存储sum的变量，平均空间复杂度为O(1)。

        咋一看这个方法还不错，O(n)的复杂度，也是实践可行的，但是会不会有可能有更好的方法呢？

        方法2，另外一个方法：

        计算机世界中，为了平衡性，运算时间和存储空间之间进行转换是常有的事情。对于上面这个问题，假如我们预先存储一些计算结果，会不会让计算的时间更快一点。

        需求1：使用一个新的数组，定义为 int[] s = new int[n];，该数组中每一个元素，存储的是原始数组中，从第0个元素到该元素的累加和，比如 s[i] = data[0] + .... + data[i]。这样的话，计算 sum(i, j)，只要做一次计算就可以，sum(i, j) = s[j] - s[i - 1];。

        需求2：修改元素data[i] 的话，需要对 s 数组的 [0 ~ i] 进行更新。

        示例图：

        性能分析：

       时间复杂度：需求1，构建数组s需要O(n)的时间，但是只需要构建一次，整体操作次数越多，影响越小，这里先忽略不计，   求和的时候，只需要做一次减法，所以平均复杂度为 O(1)。需求2，每次按索引对数组进行修改，都要修改数组s，所以平均时间复杂度为O(n)。需求3：由于需求1和需求2操作频率相当，所以需求3的平均时间复杂度为O(n)。

        空间复杂度：需要存储一个额外的数组s，所以平均空间复杂度为O(n)。

        咋一看这个方法还不如让方法1，让人很不开心。但是方法2却是让我们在前进的道路上迈出了跨越性的一步，就是空间换时间。

        好吧，空间换时间是吧，方法2也是啊，怎么就不好用呢，仔细思考方法2，会发现方法2的一个特性，就是子问题是重叠的，也就是说 s[j] 内部是隐含包括 s[i] 的（i <= j）。在某种程度上，这是一个动态规划的思想。为什么子问题重叠不行呢，假如有索引（i <= j <= k）,如果我需要计算 sum(j, k) = s[k] - s[j - 1]; ,如果现在修改了data[i] ,对 sum(j, k) 的结果是毫无影响的，但是修改了data[i]后，需要对 s[k] 和 s[j] 的公共子问题 s[i] 进行修改，而这种修改是不必要的。

        既然问题分解成更小规模后，有重叠子问题这种情况，不适用于这个问题，那么考虑一下子问题不重叠的情况呢？这也就是分治思想。

        方法3，换个方法分解问题：

        把原始数组data，连续两个元素进行合并，合并的节点为这两个数据的父节点，父节点的数据为两个子节点的和，然后一直这样重复，直到最后合并为只有一个节点。

        示例图：

        需求1：如果需要计算 sum(i, j)，从整个树的根节点开始查找，根据查询边界（也就是i和j）和节点表示的范围进行比较，然后一直查询到树的叶子节点。比如我们要查询 sum(2， 6),如图所示，只需要计算这几个绿色节点的和就可以了。

        需求2：修改元素data[i] 的话，需要对该节点网上的所有父节点进行更新，比如更新data[5]，如下图所示，也就是红色节点。

        性能分析：

       时间复杂度：需求1，构建树需要O(log2n)的时间，但是只需要构建一次，整体操作次数越多，影响越小，这里先忽略不计，   求和的时候，从根节点一直搜索到叶子节点，所以平均复杂度为 O(log2n)。需求2，每次按索引对数组进行修改，都要修改整个树，但是只需要修改被修改节点的父节点，所以平均时间复杂度为O(log2n)。需求3：由于需求1和需求2操作频率相当，所以需求3的平均时间复杂度为O(log2n)。

        空间复杂度：需要存储一个额外的树，所以平均空间复杂度为O(n)。

        这下看起来有点效果了，花费了n的空间，换来了O(logn)的时间复杂度。

Segment Tree

        简介：Segment Tree，也叫区间树，是一种按区间来存储一个序列的某些信息的数据结构。很适合来解决上面提到的问题。详细信息参考连接：https://en.wikipedia.org/wiki/Segment_tree

        上面的方法3的思想，和区间树的思想是差不多的，都是构建成一颗完全二叉树。

        区间树可以存储任何区间信息，比如某个区间的最小值，或者某个区间的最大值，或者某个区间的和（上面提到的问题），等等。。

        构建一颗区间树：

        自顶向下的递归法：

        1、把数组一分为二，生成一个节点，节点的信息为左半边数组和右半边数组信息的聚集。

        2、重复步骤1，直到所有叶子节点都是原始数组节点。

        示例图：

        自底向上的递推法：

        1、从后往前遍历数组，把节点两两聚合，生成父节点，碰到最后还有单个节点，就和上一层最右侧节点聚合，往更高一层聚合。

        2、重复步骤1，直到最后只有一个节点。

        示例图：

        由于递归法能直接反应该问题的性质，所以递归法比较容易理解问题。但是递归在实际使用中，性能堪忧，很容易造成方法栈溢出，所以在实际编码的时候，基本都使用自底向上的递推法。

使用 Segment Tree 解决上述问题的代码

        1、由于最后构造的树是一颗完全二叉树，所以整棵树节点数量是 2*n - 1。

        2、完全二叉树可以使用一个数组存储，因为如果一个节点位于索引i处，那么父节点为 i/2，左右子节点为 2*i，2*i + 1。

        3、注意，0索引位置不使用，因为有乘除法，所以如果索引为0的话，不能正确找到父子节点。

class NumArray {

    int[] st;
    int[] nums;

    public NumArray(int[] nums) {
        this.nums = nums;

        st = new int[nums.length * 2];
        construct(st, 1, nums, 0, nums.length - 1);
    }

    private void construct(int[] st, int stIndex, int[] data, int dataStartIndex, int dataEndIndex) {
        System.arraycopy(data, 0, st, st.length - data.length, data.length);
        for (int i = st.length - data.length - 1; i > 0; i--) {
            st[i] = st[i << 1] + st[(i << 1) + 1];
        }
    }

    public void update(int i, int val) {
        int index = st.length - nums.length + i;
        st[index] = val;

        index = index / 2;
        while (index >= 1) {
            st[index]  = st[index << 1] + st[(index << 1) + 1];
            index = index / 2;
        }
    }

    public int sumRange(int i, int j) {

        int sum = 0;

        i = i + nums.length;
        j = j + nums.length;

        //if i == j, loop finish, sum = st[i]
        while (i <= j) {

            //parent intersectcover
            if (i % 2 == 1) {
                sum += st[i];
                i++;
                continue;
            }
            if (j % 2 == 0) {
                sum += st[j];
                j--;
                continue;
            }

            //parent contain, up to parent
            i  = i >> 1;
            j  = j >> 1;

        }

        return sum;
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(i,val);
 * int param_2 = obj.sumRange(i,j);
 */

使用 Segment Tree 存储隐藏信息

1、http://www.spoj.com/problems/BRCKTS/

        使用Segment Tree来存储什么信息？当一个区间中，'('  的数量和  ')' 的数量一样，并且成功匹配的数量也和他们相等时，就是正确的，每一次聚合，我们可以根据左右节点的左右括号数量和已匹配数量，来计算父节点的信息。使用区间树来存储左右括号数量和匹配数量。

2、https://leetcode.com/problems/count-of-smaller-numbers-after-self/description/

        使用Segment Tree来存储什么信息？先拷贝一份原始数组，然后对拷贝数组进行排序，然后从后往前遍历原始数组，每遍历一个值，找出它在排序后的索引，然后计算从0到当前索引的数据个数，然后把该索引数据个数加1。使用区间树来存储数据出现的次数。

Fenwick Tree（Binary Indexed Tree / BIT）

        BIT在功能上可以看成是一个特殊的区间树。也是存储某个区间的信息。

        参考链接：https://en.wikipedia.org/wiki/Fenwick_tree

        示例图：

       

        区间树的区间是二分形成，而BIT的区间划分规则是这样的：

        假如索引为index = 10；又因为10的二进制表示为1010，只保留最右边的1，去掉左边其他所有的1后，变为0010，也就是2，所以，index的区间为[index - 2 + 1, index]。

        BIT的读取和写入操作都是自底向上的

        读操作，父节点索引为 index - index & (-index)。

        示例图：

      

        写操作，父节点索引为 index + index & (-index)。

        示例图：

         他与区间树的区别在于，BIT的代码更简洁，也更省空间。因为BIT不需要额外的存储原始数据信息。因为区间树的叶子节点是原始数据，所以需要的存储空间比BIT多。

        使用BIT解决上面的问题：

class NumArray1 {
    int bit[];
    int[] data;

    public NumArray1(int[] nums) {
        buildBIT(nums);
    }

    private void buildBIT(int[] nums) {
        this.data = new int[nums.length];

        bit = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            update(i, nums[i]);
            this.data[i] = nums[i];
        }
    }

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

    public void update(int i, int val) {

        int delta = val - data[i];
        i++;
        while (i <= data.length) {
            bit[i] += delta;
            i += i & (-i);
        }
    }

    private int sum(int endIndex) {
        endIndex++;
        int sum = 0;
        while (endIndex > 0) {
            sum += bit[endIndex];
            endIndex -= endIndex & (-endIndex);
        }
        return sum;
    }

}