Solving Range Sum Query - Mutable

class NumArray {
public:
    NumArray(vector<int> nums) {
       
        Image.push_back(vector<int>(nums));
        int size = nums.size();
        int level = 1;
        while(size >= 10)
        {
            Image.push_back(vector<int>(size/10, 0));
           
            for(int i = 0; i < size/10; i++)
            {
                int localSum = 0;
                for(int j = 0; j < 10; j++)
                    localSum += Image[level-1][10*i+j];
                   
                Image[level][i] = localSum;
            }

            size /= 10;
            level += 1;
        }
    }
   
    void update(int i, int val) {
       
        int diff = val - Image[0][i];
        Image[0][i] = val;
       
        for(int level = 1; level < Image.size(); level++)
        {
            i /= 10;
            Image[level][i] += diff;
        }
    }
   
    int sumRange(int i, int j) {
       
        if(i == j)
            return Image[0][i];
           
        int sum = Image[0][j];
        int level = 0;

        while(true)
        {
            while(i % 10 != 0 && i != j)
            {
                sum += Image[level][i];
                i++;
            }
           
            while(j % 10 != 0 && j != i)
            {
                j--;
                sum += Image[level][j];
            }
           
            // escape condition
            if(i == j)
            {
                break;
            }
           
            level++;
            i /= 10;
            j /= 10;
        }
       
        return sum;
    }
   
private:
    vector<vector<int>> Image;
};

留言

這個網誌中的熱門文章

大彎國家公園: 四日行程 Four Days in Marfa & Big Bend