Data Structures - Segment Trees

Question

I was learning about segment trees and came across this:

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 to a new value x. We need to do arr[i] = x where 0 <= i <= n-1.

A simple solution is to run a loop from l to r and calculate sum of elements in given range. To update a value, simply do arr[i] = x. The first operation takes O(n) time and second operation takes O(1) time.

Another solution is to create another array and store sum from start to i at the ith index in this array. Sum of a given range can now be calculated in O(1) time, but update operation takes O(n) time now. This works well if the number of query operations are large and very few updates.

This is quoted from this web page.

The paragraph which I'm confused with is marked as bold. I think that the sum of a given range will only be calculated in O(1) time if l = 0, which is not always the case. Also, I can't seem to understand why did the update operation now takes O(n) time.

I hope it's just a small problem that can be easily explained. You can even explain the whole concept of segment trees here. I appreciate any help in any ways. Thanks.

Answer 1

Suppose you have created another array $S$ and stored sum from start to $i$ at $S[i]$. The sum of elements from index $l$ to $r$ inclusive is $S[r]-S[l-1]$ for $l\ge1$, which takes two lookups and one subtraction, or $S[r]$ for $l=0$, which takes one lookup. So it takes $O(1)$ time.

Suppose you set $arr[k]$ to a new value, where $k=n/3$. Then you have to update $S[k], S[k+1], \cdots, S[n-1]$, which are roughly $n-n/3=2n/3$ numbers. That is, it takes $O(n)$ time. You can figure out all other cases of $k$.

"You can even explain the whole concept of segment trees here." That is exactly the purpose of that article and its follow-ups. Try reading them. Follow the recommendations thereof.