## 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