Sum of range using Nested Loop
A simple solution is to run a loop from l to r and calculate the sum of elements in the given range. To update a value, simply do arr[i] = x. The first operation takes O(n) time and the second operation takes O(1) time.
Segment Tree | Sum of given range
Let us consider the following problem to understand Segment Trees.
We have an array arr[0 . . . n-1]. We should be able to
- Find the sum of elements from index l to r where 0 <= l <= r <= n-1
- Change the 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.