Range Query on a List - Mutable - Google Top Interview Questions

                        Solution in C++ :

#pragma GCC optimize("Ofast")
#pragma GCC target("tune=native")
#pragma GCC optimize("unroll-loops")
class MutableRangeSum {
    int n, len;
    vector<int> nums, blocks;

    public:
    MutableRangeSum(vector<int>& nums) {
        n = (int)nums.size();
        len = sqrt(n);
        this->nums = nums;
        blocks.assign(n / len, 0);
        for (int i = 0; i < n; i++) blocks[i / len] += nums[i];
    }
    int total(int i, int j) {
        int sum = 0;
        for (int x = i; x < j;)
            if (x % len == 0 && x + len < j)
                sum += blocks[x / len], x += len;
            else
                sum += nums[x++];
        return sum;
    }
    void update(int idx, int val) {
        blocks[idx / len] += val - nums[idx];
        nums[idx] = val;
    }
};
                    

                        Solution in Java :

import java.util.*;

class SegmentTree {
    int size;
    long[] operations;

    SegmentTree(int n) {
        this.size = 1;
        while (size < n) size *= 2;
        operations = new long[size * 2];
    }

    void set(int idx, int val) {
        set(idx, val, 0, 0, size);
    }

    void set(int idx, int val, int x, int lx, int rx) {
        if (rx - lx == 1) {
            operations[x] = val;
            return;
        }
        int mx = (rx + lx) / 2;
        if (idx < mx) {
            set(idx, val, 2 * x + 1, lx, mx);
        } else {
            set(idx, val, 2 * x + 2, mx, rx);
        }
        operations[x] = operations[2 * x + 1] + operations[2 * x + 2];
    }

    long query(int l, int r) {
        return query(l, r, 0, 0, size);
    }

    long query(int l, int r, int x, int lx, int rx) {
        if (lx >= r || l >= rx)
            return 0;
        if (lx >= l && rx <= r)
            return operations[x];
        int mx = (lx + rx) / 2;
        long left = query(l, r, 2 * x + 1, lx, mx);
        long right = query(l, r, 2 * x + 2, mx, rx);
        return left + right;
    }
}
class MutableRangeSum {
    SegmentTree st;
    public MutableRangeSum(int[] nums) {
        st = new SegmentTree(nums.length);
        for (int i = 0; i < nums.length; i++) {
            st.set(i, nums[i]);
        }
    }

    public int total(int i, int j) {
        return (int) st.query(i, j);
    }

    public void update(int idx, int val) {
        st.set(idx, val);
    }
}
                    

                        Solution in Python : 
                            
class Fenwick:
    def __init__(self, n):
        self.items = [0] * (n + 1)

    def update(self, idx, val):
        while idx < len(self.items):
            self.items[idx] += val
            idx += idx & -idx

    def get_sum(self, idx):
        res = 0
        while idx > 0:
            res += self.items[idx]
            idx -= idx & -idx
        return res

    def get_range_sum(self, l, r):
        return self.get_sum(r - 1) - self.get_sum(l - 1)


class MutableRangeSum:
    def __init__(self, nums):
        self.fw = Fenwick(len(nums))
        for i in range(len(nums)):
            self.fw.update(i + 1, nums[i])

    def total(self, i, j):
        return self.fw.get_range_sum(i + 1, j + 1)

    def update(self, idx, val):
        cur_val = self.fw.get_sum(idx + 1) - self.fw.get_sum(idx)
        self.fw.update(idx + 1, val - cur_val)