Range Sum Query - Mutable Solutions in C++

// Source : https://leetcode.com/problems/range-sum-query-mutable/
// Author : Hao Chen
// Date   : 2015-11-24




// The following idea is using `Binary Index Tree`
// There are two articles explaine this technique quite well:
// 1) http://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/
// 2) http://cs.stackexchange.com/questions/10538/bit-what-is-the-intuition-behind-a-binary-indexed-tree-and-how-was-it-thought-a

class NumArray {
private:
    int _sz;
    vector<int> _nums;
    vector<int> _sums;    
public:
    NumArray(vector<int> &nums)  {
        _sz = nums.size();
        _nums.resize(_sz+1, 0);
        _sums.resize(_sz+1, 0);
        for(int i=0; i< _sz; i++) {
            update(i, nums[i]);          
        }
    }

    void update(int i, int val) {
        int oldv = _nums[i+1];
        for(int idx = i+1; idx <= _sz; idx += (idx & (-idx))  ) {
            _sums[idx] = _sums[idx] - oldv + val;
        }
        _nums[i+1] = val;
    }

    int sumRange(int i, int j) {
        return sumRange(j+1) - sumRange(i);
    }
    
    int sumRange(int i) {
        int ret = 0;
        for(int idx=i; idx>0; idx -= (idx & (-idx)) ) {
            ret += _sums[idx];
        }
        return ret;
    }
};


// Your NumArray object will be instantiated and called as such:
// NumArray numArray(nums);
// numArray.sumRange(0, 1);
// numArray.update(1, 10);
// numArray.sumRange(1, 2);

/// Source : https://leetcode.com/problems/range-sum-query-mutable/description/
/// Author : liuyubobobo
/// Time   : 2017-10-28

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

/// Segment Tree
/// Time Complexity: update: O(logn)
///                  query: O(logn)
/// Space Complexity: O(n)
class SegmentTree{

private:
    vector<int> tree;
    vector<int> nums;

public:
    SegmentTree(const vector<int>& nums){

        if(nums.size() == 0)
            return;

        for(int num: nums)
            (this->nums).push_back(num);

        int size = 4*nums.size();
        for(int i = 0 ; i < size ; i ++)
            tree.push_back(-1);

        treeBuild(0, 0, nums.size()-1);
    }

    void update(int index, int val){
        assert(index >= 0 && index < nums.size());
        nums[index] = val;
        update(0, 0, nums.size()-1, index, val);
    }

    int query(int l, int r){
        assert(l >= 0 && l < nums.size());
        assert(r >= 0 && r < nums.size());
        return query(0, 0, nums.size()-1, l, r);
    }

    void print(){
        for(int e: tree)
            cout << e << " ";
        cout << endl;
    }

private:
    void treeBuild(int treeID, int nodeLeftBound, int nodeRightBound){

        assert(nodeLeftBound <= nodeRightBound);
        if(nodeLeftBound == nodeRightBound){
            tree[treeID] = nums[nodeLeftBound];
            return;
        }

        int mid = (nodeLeftBound + nodeRightBound) / 2;
        treeBuild(treeID * 2 + 1, nodeLeftBound, mid);
        treeBuild(treeID * 2 + 2, mid + 1, nodeRightBound);

        tree[treeID] = tree[treeID * 2 + 1] + tree[treeID * 2 + 2];
    }

    void update(int treeID, int nodeLeftBound, int nodeRightBound, int index, int val){

        assert(nodeLeftBound <= nodeRightBound);
        if(nodeLeftBound == nodeRightBound){
            assert(index == nodeLeftBound);
            tree[treeID] = val;
            return;
        }

        int mid = (nodeLeftBound + nodeRightBound)/2;
        if(index >= nodeLeftBound && index <= mid)
            update(treeID * 2 + 1, nodeLeftBound, mid, index, val);
        else
            update(treeID * 2 + 2, mid+1, nodeRightBound, index, val);

        tree[treeID] = tree[treeID * 2 + 1] + tree[treeID * 2 + 2];
    }

    int query(int treeID, int nodeLeftBound, int nodeRightBound, int l, int r){

        if(l == nodeLeftBound && r == nodeRightBound)
            return tree[treeID];

        int mid = (nodeLeftBound + nodeRightBound) / 2;
        if(r <= mid)
            return query(treeID * 2 + 1, nodeLeftBound, mid, l, r);
        if(l >= mid + 1)
            return query(treeID * 2 + 2, mid + 1, nodeRightBound, l, r);

        return query(treeID * 2 + 1, nodeLeftBound, mid, l, mid) +
                query(treeID * 2 + 2, mid + 1, nodeRightBound, mid + 1, r);
    }
};

class NumArray {

private:
    SegmentTree tree;

public:
    NumArray(vector<int> nums):tree(nums) {}

    void update(int i, int val) {
        tree.update(i, val);
    }

    int sumRange(int i, int j) {
        return tree.query(i, j);
    }
};


int main() {

    vector<int> nums1 = {1, 3, 5};
    NumArray obj1(nums1);

    cout << obj1.sumRange(0, 2) << endl;
    obj1.update(1, 2);
    cout << obj1.sumRange(0, 2) << endl;

    cout << endl;

    // ---

    vector<int> nums2 = {0, 9, 5, 7, 3};
    NumArray obj2(nums2);

    cout << obj2.sumRange(4, 4) << endl;
    cout << obj2.sumRange(2, 4) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/range-sum-query-mutable/description/
/// Author : liuyubobobo
/// Time   : 2019-08-11

#include <iostream>
#include <vector>
#include <cassert>
#include <cmath>
#include <numeric>
#include <algorithm>

using namespace std;

/// Bucket
/// Time Complexity: init: O(n)
///                  update: O(logn)
///                  query: O(sqrt(n))
/// Space Complexity: O(n)
class NumArray {

private:
    vector<int> bucket, arr, sum;
    const int bucket_sz;

public:
    NumArray(vector<int> nums): arr(nums.begin(), nums.end()), bucket_sz(sqrt(arr.size())) {

        bucket.push_back(0);
        while(bucket.back() != nums.size()){
            int l = bucket.back();
            int r = min(bucket.back() + bucket_sz, (int)nums.size());
            bucket.push_back(r);
            sum.push_back(accumulate(nums.begin() + l, nums.begin() + r, 0));
        }

//        cout << "bucket_sz = " << bucket_sz << endl;
//        for(int e: bucket) cout << e << " "; cout << endl;
//        for(int e: sum) cout << e << " "; cout << endl;
    }

    void update(int i, int val) {
        int o = arr[i];
        arr[i] = val;

        vector<int>::iterator iter = lower_bound(bucket.begin(), bucket.end(), i);
        int index = iter - bucket.begin();
        if(bucket[index] != i) index --;

        sum[index] = sum[index] - o + val;
    }

    int sumRange(int i, int j) {

        vector<int>::iterator iter = lower_bound(bucket.begin(), bucket.end(), i);
        int index = iter - bucket.begin();
        if(bucket[index] != i) index --;

        if(i >= bucket[index] && j < bucket[index + 1]) return sumNaive(i, j);

        int res = sumNaive(i, bucket[index + 1] - 1);
        index ++;
        while(j >= bucket[index]){

            if(j < bucket[index + 1]) res += sumNaive(bucket[index], j);
            else res += sum[index];

            index ++;
        }
        return res;
    }

private:
    int sumNaive(int i, int j){
        return accumulate(arr.begin() + i, arr.begin() + (j + 1), 0);
    }
};


int main() {

    vector<int> nums1 = {1, 3, 5};
    NumArray obj1(nums1);

    cout << obj1.sumRange(0, 2) << endl;
    obj1.update(1, 2);
    cout << obj1.sumRange(0, 2) << endl;

    cout << endl;

    // ---

    vector<int> nums2 = {0, 9, 5, 7, 3};
    NumArray obj2(nums2);

    cout << obj2.sumRange(4, 4) << endl;
    cout << obj2.sumRange(2, 4) << endl;

    return 0;
}