In a range update question, I want to add a value to array elements in a range. It can be assumed that the array (or some data structure) is sorted.
A naive algorithm would be to loop through the starting element to the ending element and add a value v to each element.
But that takes O(n) time in the worst case when the range is from the first to last element. Is there a faster way to do this? Should I use segment tree to do it?
If the array is really a c style array (not necessarily sorted) and not a tree like data structure which already implicitly includes its order in its structure O(n) is the best you can get.
There are other data structures (trees Of various sorts that would allow faster lookup. However, converting an unsorted array to one of these structures will always be worse than O(n).