摘要：題目要求可以先參考數(shù)組不發(fā)生變動(dòng)時(shí)的題目。最后的葉節(jié)點(diǎn)為當(dāng)前數(shù)組的值，非葉結(jié)點(diǎn)則記錄了子數(shù)組的范圍以及該子數(shù)組中所有元素的和。它是一個(gè)非常輕量級(jí)的數(shù)據(jù)結(jié)構(gòu)，而且?guī)缀蹙褪菫檫@種題目量身打造。

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.
Example:
Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8
Note:
The array is only modifiable by the update function.
You may assume the number of calls to update and sumRange function is distributed evenly.

可以先參考數(shù)組不發(fā)生變動(dòng)時(shí)的題目。

這里的難度在于數(shù)組可以在中間出現(xiàn)變動(dòng)，那么面對(duì)大容量數(shù)組的時(shí)候如何選擇一個(gè)合適的數(shù)據(jù)結(jié)構(gòu)及很重要。

最開始我們有兩種直觀的想法，一種是在插入時(shí)同時(shí)更新后面所有的和，這意味著O(n)的插入復(fù)雜度和O(1)的讀取復(fù)雜度。我決定選擇第二種方式，也就是采用類似日志的形式記錄下每一次的變更。這樣當(dāng)我們讀取的時(shí)候，再遍歷日志，將相關(guān)的變更結(jié)果添加到當(dāng)前的數(shù)值上。缺點(diǎn)是，變更很多以及數(shù)組很龐大時(shí)，效率依然很差。

這個(gè)方法超時(shí)了。

private int[] sum;
    private int[] nums;
    private Map log;
    public NumArray(int[] nums) {
        this.nums = nums;
        sum = new int[nums.length];
        for(int i = 0 ; i();
    }
    
    public void update(int i, int val) {
        log.put(i, val - nums[i]);
    }
    
    public int sumRange(int i, int j) {
        int origin = 0;
        if(i==0) origin = sum[j];
        else origin = sum[j] - sum[i-1];
        for(Integer key : log.keySet()){
            if(key>=i && key <= j){
                origin += log.get(key);
            }
        }
        return origin;
    } 

我們將一個(gè)數(shù)組轉(zhuǎn)化為一棵樹，其中當(dāng)前的數(shù)組被均勻的分割并且分別用左子數(shù)組和右子數(shù)組構(gòu)建左子樹和右子樹。最后的葉節(jié)點(diǎn)為當(dāng)前數(shù)組的值，非葉結(jié)點(diǎn)則記錄了子數(shù)組的范圍以及該子數(shù)組中所有元素的和。

舉個(gè)例子說明一下：
假設(shè)當(dāng)前的數(shù)組為[1,2,5]，則構(gòu)成的Segment Tree為：

        8
       / 
      3   5
     / 
    1   2

這里先將[1,2,5]分割為[1,2]和[5]兩個(gè)子數(shù)組，然后分別構(gòu)造子樹。最后的樹如上所示。

    class SegmentTreeNode{
        int start;
        int end;
        SegmentTreeNode left;
        SegmentTreeNode right;
        int sum;
        
        public SegmentTreeNode(int start, int end){
            this.start = start;
            this.end = end;
        }
    }
    
    private SegmentTreeNode buildSegmentTree(int[] nums, int start, int end){
        if(start > end) return null;
        SegmentTreeNode cur = new SegmentTreeNode(start, end);
        if(start == end) cur.sum = nums[start];
        else{
            int mid = (start + end) / 2;
            cur.left = buildSegmentTree(nums, start, mid);
            cur.right = buildSegmentTree(nums, mid+1, end);
            cur.sum = cur.left.sum + cur.right.sum;
        }
        return cur;
    }
    
    private SegmentTreeNode root;
    public NumArray(int[] nums) {
        this.root = buildSegmentTree(nums, 0, nums.length-1);
    }
    
    public void update(int i, int val) {
        update(root, i, val);
    }
    
    private void update(SegmentTreeNode root, int position, int val){
        if(root.start == root.end){
            root.sum = val;
        }else{
            int mid = (root.start + root.end) / 2;
            if(position <= mid){
                update(root.left, position, val);
            }else{
                update(root.right, position, val);
            }
            root.sum = root.left.sum + root.right.sum;
        }
    }
    
    public int sumRange(int i, int j) {
        return sumRange(root, i, j);
    }    
    
    public int sumRange(SegmentTreeNode root, int i, int j){
        if(root.start==i && root.end==j){
            return root.sum;
        }
        int mid = (root.start + root.end )/2;
        if(j<=mid){
            return sumRange(root.left, i, j);
        }else if(i>mid){
            return sumRange(root.right, i, j);
        }else{
            return sumRange(root.left, i, mid) + sumRange(root.right, mid+1, j);
        }
    }

要想了解更多關(guān)于Segment Tree，請(qǐng)參考這篇文章。

網(wǎng)上有非常多的關(guān)于二進(jìn)制索引數(shù)樹的教程。它是一個(gè)非常輕量級(jí)的數(shù)據(jù)結(jié)構(gòu)，而且?guī)缀蹙褪菫檫@種題目量身打造?？梢韵葟倪@篇文章和這篇文章了解一下。

    class NumArray {
           int[] nums;
            int[] BIT;
            int n;

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

                n = nums.length;
                BIT = new int[n + 1];
                for (int i = 0; i < n; i++)
                    init(i, nums[i]);
            }

            //每次更新當(dāng)前節(jié)點(diǎn)的同時(shí)更新父節(jié)點(diǎn)
            public void init(int i, int val) {
                i++;
                while (i <= n) {
                    BIT[i] += val;
                    i += (i & -i);
                }
            }

            //更新當(dāng)前節(jié)點(diǎn)，同時(shí)將改變傳遞給父節(jié)點(diǎn)
            void update(int i, int val) {
                int diff = val - nums[i];
                nums[i] = val;
                init(i, diff);
            }

            //
            public int getSum(int i) {
                int sum = 0;
                i++;
                while (i > 0) {
                    sum += BIT[i];
                    i -= (i & -i);
                }
                return sum;
            }

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

想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~