Find sum of all elements of an array excluding index L to R

Question

We have an array arr[0 . . . n-1]. We should be able to

1. Find the sum of elements from index L to R where 0 <= L <= R <= n-1 .
2. Change value of a specified element of the array arr[i] = x where 0 <= i <= n-1.

This can be solved using segment tree efficiently .

But how to solve opposite to this i.e.

1. Find the sum of all elements (arr[i]) from index 0 to n-1 excluding L<= i <= R where L and R are given.
2. Change value of a specified element of the array arr[i] = x where 0 <= i <= n-1.

How to solve above question efficiently like segment tree?

Answer 1

Assuming you can calculate sum(L,R) easily with segment tree.

First, calculate the total sum of whole array, called it total.

For a change in the arr at position ith

• Update the segment tree as usual.

• Update total = total - oldValue + newValue.

For each query , print total - sum(L,R)

Note: we can use binary indexed tree (a.k.a Fenwick tree) for this problem too, which IMO, is more suitable.