前言

在刷題過(guò)程中，經(jīng)常會(huì)遇到求數(shù)組某區(qū)間之和的問(wèn)題：給出數(shù)組a[0...n-1]完疫，求數(shù)組下標(biāo)i~j的元素之和a[i]+...+a[j]扔涧，0<=i<=j<n。
純暴力做法是O(n)旨椒，即把區(qū)間的數(shù)加起來(lái)。
好一點(diǎn)辦法的是創(chuàng)建一個(gè)前綴和（prefix sum）數(shù)組p堵漱，使得p[i]=a[0]+...+a[i]综慎，那么所求結(jié)果就是p[j]-p[i-1]，當(dāng)然i=0需要特別處理一下勤庐。這樣準(zhǔn)備工作是O(n)示惊，查詢只需要O(1)。
一般來(lái)說(shuō)愉镰，數(shù)組不變的情況下方法二已經(jīng)夠用了米罚。但是當(dāng)數(shù)組有可能改變的時(shí)候，每次改變都需要更新前綴和數(shù)組丈探，效率不高录择。
好在，有專門(mén)的數(shù)據(jù)結(jié)構(gòu)來(lái)滿足這種操作需求碗降。今天我們就來(lái)簡(jiǎn)單學(xué)習(xí)一下線段樹(shù)（Segment Tree）和樹(shù)狀數(shù)組（Fenwick Tree）隘竭。

線段樹(shù)

顧名思義，線段樹(shù)是樹(shù)遗锣。具體一點(diǎn)货裹，二叉樹(shù)。那么“線段”二字如何體現(xiàn)精偿？是把i-j區(qū)間之和想象成i-j的線段（我瞎猜的）弧圆。簡(jiǎn)而言之赋兵，線段樹(shù)就是把區(qū)間之和用樹(shù)來(lái)顯示。
很自然地搔预，根是整個(gè)數(shù)組區(qū)間霹期，然后左右分半，依次類推拯田。奇數(shù)情況下是左邊多還是右邊多呢历造？其實(shí)都可以，不過(guò)考慮區(qū)間[a,b]船庇，最自然的寫(xiě)法可分為[a,(a+b)/2]與[(a+b)/2,b]吭产，當(dāng)b-a是奇數(shù)時(shí)右邊多，這樣寫(xiě)起來(lái)更自然方便些鸭轮。
從網(wǎng)上搜了個(gè)圖臣淤，這樣更直觀：

image.png

怎么構(gòu)造這棵樹(shù)呢？
首先要決定樹(shù)的節(jié)點(diǎn)窃爷。左右子節(jié)點(diǎn)等屬性是很自然的邑蒋。同時(shí)需要存儲(chǔ)表示的區(qū)間，以及區(qū)間之和按厘。
需不需要指針指向parent節(jié)點(diǎn)呢医吊？大可不必。
至于重要的幾個(gè)操作逮京，構(gòu)造卿堂，查詢，更新造虏，抓住遞歸的特點(diǎn)御吞，自下而上地進(jìn)行，一切都顯得自然了漓藕。
構(gòu)造：遞歸，先構(gòu)造左右挟裂，再構(gòu)造自己享钞，這樣其實(shí)是從底層往上構(gòu)造。
查詢：同樣遞歸诀蓉，假如查詢的區(qū)間就是自己馬上返回栗竖，否則就有三種情況：查詢左邊，查詢右邊渠啤，兩邊都有狐肢。
更新：和查詢類似，不同的是一次只更新一個(gè)元素沥曹，所以只會(huì)走一邊份名。路徑相當(dāng)于查詢[i,i]碟联，下到最底層更新值。注意路徑之上的節(jié)點(diǎn)也要跟著更新和僵腺。
當(dāng)然了鲤孵，start和end在這里是inclusive的，和java傳統(tǒng)慣例有點(diǎn)不一樣辰如，但是這系列的習(xí)慣好像就這樣普监，畢竟要表示單個(gè)元素。樹(shù)的高度是O(logn)琉兜，而查詢操作近似遍歷樹(shù)凯正，所以也是O(logn)。更新操作類似豌蟋，同樣是O(logn)漆际。構(gòu)造的話，要把節(jié)點(diǎn)都過(guò)一遍夺饲，所以是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);
    }
}

代碼量還是不小的，畢竟用了樹(shù)往声。

樹(shù)狀數(shù)組

樹(shù)狀數(shù)組（也叫Binary Indexed Tree）就是指用數(shù)組來(lái)表示一棵樹(shù)擂找，這樣空間上更節(jié)約。類似的還有binary heap浩销。
那么樹(shù)怎么放進(jìn)數(shù)組呢贯涎？根據(jù)維基百科，對(duì)于數(shù)組里的下標(biāo)i進(jìn)行一個(gè)特定的位運(yùn)算慢洋，就可以獲得其父節(jié)點(diǎn)所在的下標(biāo)塘雳。聽(tīng)起來(lái)很神奇？剛開(kā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;
    }
}

可見(jiàn)未檩，其實(shí)樹(shù)狀數(shù)組并不是簡(jiǎn)單地把線段樹(shù)裝進(jìn)數(shù)組戴尸，而是有另一套計(jì)算方法，差別還是挺明顯的冤狡。
相比之下孙蒙，樹(shù)狀數(shù)組代碼量更少，更高效悲雳，一般來(lái)說(shuō)是更好的選擇挎峦。

例題

Range Sum Query - Mutable - LeetCode
以上兩種實(shí)現(xiàn)改個(gè)名字就可以直接當(dāng)答案了。