Interval SumII

Given an integer array in the construct method, implement two methodsquery(start, end) andmodify(index, value): • For query(start, end), return thesum from index start to indexend in the given array. • For modify(index, value), modify the number in the given index to value Have you met this question in a real interview? Yes Example Given array A = [1,2,7,8,5]. • query(0, 2), return 10. • modify(0, 4), change A[0] from 1 to 4. • query(0, 1), return 6. • modify(2, 1), change A[2] from 7 to 1. • query(2, 4), return 14.

sqrt solution

基本思想是把数组划分成sqrt(n)+1部分，每一部分是sqrt(n)个数的和。每一次查询总求和次数不会超过sqrt(n)*3。可能时间复杂度有点高，但是修改值的复杂度是O(1). 这个算法原来是用topcoder 的 RMQ，我把它改成求和，总体思路是类似的。

class Solution {
public:
    /* you may need to use some attributes here */


    /**
     * @param A: An integer vector
     */
    Solution(vector<int> A) {
        // write your code here
        nums=A;
        sqrtn=sqrt(A.size());

        //here, it need to be sqrtn+2!!!
        sqrtSum=vector<long long>(sqrtn+2,0);

        int idx=0;

        for(int i=0;i<=sqrtn;i++)
        {
            for(int j=0;j<sqrtn;j++)
            {
                if(i*sqrtn+j>=A.size())break;
                sqrtSum[i]+=nums[i*sqrtn+j];
            }
        }
    }

    /**
     * @param start, end: Indices
     * @return: The sum from start to end
     */
    long long query(int start, int end) {
        // write your code here
        if(start>end)return 0;
        if(start==end)return nums[start];

        int fsqrt=start/sqrtn;
        int lsqrt=end/sqrtn;


        long long total=0;

        if(fsqrt==lsqrt)//
        {
            for(int i=start;i<=end;i++)total+=nums[i];
        }
        else
        {
            //here, we need to pay attention to +sqrtn!!,otherwise always smaller, no add
            for(int i=start;i<fsqrt*sqrtn+sqrtn;i++)total+=nums[i];

            for(int i=fsqrt+1;i<lsqrt;i++)total+=sqrtSum[i];

            for(int i=lsqrt*sqrtn;i<=end;i++)total+=nums[i];

        }


        return total;
    }

    /**
     * @param index, value: modify A[index] to value.
     */
    void modify(int index, int value) {
        // write your code here
        int idx=index/sqrtn;
        sqrtSum[idx]+=(value-nums[index]);
        nums[index]=value;
    }

    int sqrtn;
    vector<int>  nums;
    vector<long long> sqrtSum;
};

Binary Index Tree

Very good article here: topcoder Binary Index Tree

• idx is some index of BIT. r is a position in idx of the last digit 1 (from left to right) in binary notation. tree[idx] is sum of frequencies from index (idx – 2^r + 1) to index idx (look at the Table 1.1 for clarification). We also write that idx is responsible for indexes from (idx - 2^r + 1) to idx (note that responsibility is the key in our algorithm and is the way of manipulating the tree).
• Integer -num is equal to (a1b)¯ + 1 = a¯0b¯ + 1. b consists of all zeroes, so b¯ consists of all ones. Finally we have
  -num = (a1b)¯ + 1 = a¯0b¯ + 1 = a¯0(0…0)¯ + 1 = a¯0(1…1) + 1 = a¯1(0…0) = a¯1b .
  Now, we can easily isolate the last digit, using bitwise operator AND (in C++, Java it is &) with num and -num:
  因此一个数字最末尾一位1的求法是num&(num-1)。

class Solution {
public:
    /* you may need to use some attributes here */


    /**
     * @param A: An integer vector
     */
    Solution(vector<int> A) {
        // write your code here
        int n=A.size();
        nums=A;
        vector<int> sum(n);

        tree=vector<int>(n);


        for(int i=0;i<n;i++)
        {
            sum[i]=((i==0)?0:sum[i-1])+A[i];
        }

        if(n>0)tree[0]=A[0];

        for(int i=1;i<n;i++)
        {
            int last=i&(-i);
            //sum from i-2^r+1 to i
            //2^r is last
            tree[i]=sum[i]-sum[i-last];
        }
    }

    /**
     * @param start, end: Indices
     * @return: The sum from start to end
     */
    long long query(int start, int end) {
        // write your code here
        if(start==0)return getSum(end);
        else return getSum(end)-getSum(start-1);
    }

    //求0-index的和部分
    int getSum(int index)
    {
        int total=tree[0];
        while(index>0)
        {
            total+=tree[index];

            //每次减去最末尾的1
            index-=(index&(-index));
        }
        return total;
    }
    /**
     * @param index, value: modify A[index] to value.
     */
    void modify(int index, int value) {
        // write your code here
        if(index==0)
        {
            tree[0]=value;
            return;
        }

        int change=value-nums[index];
        nums[index]=value;
        while(index<nums.size())
        {
            tree[index]+=change;
            //In changing some frequency val in tree, 
            //we should increment value at the current index (the starting index is always the one whose frequency is changed) for val
            //add the last digit to index and go on while the index is less than or equal to MaxVal
            index+=((index)&(-index));
        }
    }

    vector<int> tree;
    vector<int> nums;
};

Segment Tree