Flipkart Interview Question
Country: India
Interview Type: Phone Interview
To do both operations efficiently, I would go for a Binary Indexed Tree (also known as Fenwick Tree). This supports operations 1 and 2 in O(log N) time, O(N) space.
int tree[MAX], N; // indices 1..N
void Update(int x, int value) {
for (; x <= N; x += (x & -x))
tree[x] += val;
}
void GetSum(int x) {
int sum = 0;
for (; x > 0; x -= (x & -x))
sum += tree[x];
return sum;
}
Check community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees
i think the Fenwick tree for sum on array could be more appropriate. It compute sum from range [L,R] bt O(lgN) and change operation for O(lgN)
Okay, this is my solution which uses O(sqrt N) space, operation 1 can be done in O(sqrt x) and operation 2 can be done in O(1). Worse time complexity than Fenwick tree but better space complexity and better complexity for operation 2.
Store sums in an array s like this:
s[0] = sum(arr[0^2..1^2])
s[1] = sum(arr[1^2..2^2])
s[2] = sum(arr[2^2..3^2])
s[3] = sum(arr[3^2..4^2])
s[4] = sum(arr[4^2..5^2])
.
.
Extra space = O(sqrt N)
Now operation 1 can be done by adding elements of s from 0 to floor(sqrt x) + elements of arr from 2^(floor(sqrt x)) to x = O(sqrt x)
Operation 2 can be done in O(1) time, just add/subtract value t from the corresponding element in s.
1. Keep the sum array which holds the total sum from beginning to the index
- Anonymous September 18, 20132. Every time a subtract/add happens, add/subtract the value from the sum array after the index i