# Range Query on a List - 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].
Constraints

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

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

Example 1

Input

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

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

Output

[None, 8, 10]

Explanation

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

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

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

### Solution :

Solution in C++ :

class RangeSum {
public:
RangeSum(vector<int>& nums) {
n = nums.size();
sum.resize(n, 0);
sum[0] = nums[0];
for (int i = 1; i < n; ++i) {
sum[i] = sum[i - 1] + nums[i];
}
}

int total(int i, int j) {
int range = INT_MIN;
if (i >= 0 && j >= 1 && i < n && j <= n && i <= j) {
int left = i > 0 ? sum[i - 1] : 0;
int right = sum[j - 1];
range = right - left;
}
return range;
}

private:
vector<int> sum;
int n;
};

Solution in Java :

import java.util.*;

class RangeSum {
int[] pf;
public RangeSum(int[] nums) {
pf = new int[nums.length];
pf[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
pf[i] = nums[i] + pf[i - 1];
}
}
public int total(int i, int j) {
return i == 0 ? pf[j - 1] : pf[j - 1] - pf[i - 1];
}
}

Solution in Python :

class RangeSum:
def calculateprefixsum(self, vals):
vals.insert(0, 0)
for i in range(1, len(vals)):
vals[i] += vals[i - 1]
return vals

def __init__(self, nums):
self.nums = nums
self.prefixsum = self.calculateprefixsum(nums)

def total(self, i, j):
return self.prefixsum[j] - self.prefixsum[i]

## Array Pairs

Consider an array of n integers, A = [ a1, a2, . . . . an] . Find and print the total number of (i , j) pairs such that ai * aj <= max(ai, ai+1, . . . aj) where i < j. Input Format The first line contains an integer, n , denoting the number of elements in the array. The second line consists of n space-separated integers describing the respective values of a1, a2 , . . . an .

## Self Balancing Tree

An AVL tree (Georgy Adelson-Velsky and Landis' tree, named after the inventors) is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. We define balance factor for each node as : balanceFactor = height(left subtree) - height(righ

## Array and simple queries

Given two numbers N and M. N indicates the number of elements in the array A[](1-indexed) and M indicates number of queries. You need to perform two types of queries on the array A[] . You are given queries. Queries can be of two types, type 1 and type 2. Type 1 queries are represented as 1 i j : Modify the given array by removing elements from i to j and adding them to the front. Ty