CareerCup

1. Keep the sum array which holds the total sum from beginning to the index
2. Every time a subtract/add happens, add/subtract the value from the sum array after the index i

segment tree

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

The interviewer is a poor interviewer.

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.

If the array has say a 100,000 elements.
Then create a map <index,sum>
map[1000] = sum of first 1000 elements
map[2000] = sum of elements 1001 to 2000
..
..
map[100000] = sum of last 1000 elements

If 10001 element is modified. Then the value of map[10] should also be modified.