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

### Problem Statement :

```Implement a data structure with the following methods:

RangeSum(int[] nums) constructs a new instance with the given nums

total(int i, int j) returns the sum of integers from nums between [i, j). That is, nums[i] + nums[i + 1] + ... + nums[j - 1]

update(int idx, int val) updates nums[idx] with value val

Constraints

n ≤ 100,000 where n is the length of nums

k ≤ 100,000 where k is the number of calls to total

(overflows)

Example 1

Input

methods = ["constructor", "total", "update", "total"]

arguments = [[[1, 2, 5]], [0, 3], [1, 4], [0, 3]]`

Output

[None, 8, None, 10]

Explanation

r = MutableRangeSum([1,2,5,0,3,7])

r.total(0, 3) == 8 # sum([1, 2, 5])

r.update(1, 4)

r.total(0, 3) == 10 # sum([1, 4, 5])```

### Solution :

```                        ```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 =  * (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)```
```

## Down to Zero II

You are given Q queries. Each query consists of a single number N. You can perform any of the 2 operations N on in each move: 1: If we take 2 integers a and b where , N = a * b , then we can change N = max( a, b ) 2: Decrease the value of N by 1. Determine the minimum number of moves required to reduce the value of N to 0. Input Format The first line contains the integer Q.

## Truck Tour

Suppose there is a circle. There are N petrol pumps on that circle. Petrol pumps are numbered 0 to (N-1) (both inclusive). You have two pieces of information corresponding to each of the petrol pump: (1) the amount of petrol that particular petrol pump will give, and (2) the distance from that petrol pump to the next petrol pump. Initially, you have a tank of infinite capacity carrying no petr

## Queries with Fixed Length

Consider an -integer sequence, . We perform a query on by using an integer, , to calculate the result of the following expression: In other words, if we let , then you need to calculate . Given and queries, return a list of answers to each query. Example The first query uses all of the subarrays of length : . The maxima of the subarrays are . The minimum of these is . The secon

## QHEAP1

This question is designed to help you get a better understanding of basic heap operations. You will be given queries of types: " 1 v " - Add an element to the heap. " 2 v " - Delete the element from the heap. "3" - Print the minimum of all the elements in the heap. NOTE: It is guaranteed that the element to be deleted will be there in the heap. Also, at any instant, only distinct element