I am just explaining @yash_chauhan28 answer here.
Let the array be A =[1, 4, 3, 5, 2, 7, 4, 9, 8]. Divide it into segments of size BUCKET_SIZE (say ROOT(N)).
then, it will look like A = [1, 4, 3] [5, 2, 7] [4, 9, 8]. Then sort each segment separately and stor these somewhere else, DO NOT modify the array A.
for this purpose lets say we created a list of vectors B = [1, 3, 4] [2, 5, 7] [4, 9, 8]
For update query, say, add 4 from 2 to 8 (1-based indexing). Do naive updation on array A for range which partially overlap with buckets, these are the elements which lies at the extremes of the update range, and then again sort these effected buckets and update vector list B. There can be at most two effected buckets.
For segments which lies completely inside update range, just add value 4 to their lazy term.
In our example, after updation array A would be = [1, 7, 8] [2, 5, 7] [8, 13, 8]
4 --- lazy term of segment 2
and B = [1, 7, 8] [2, 5, 7] [8, 8, 13]
We just needed to sort two segments of size ROOT(N), time = O(ROOT(N) * log N)
also we needed to add value 4 to the middle segments which can be at most ROOT(N)
Total update time = O(ROOT(N) + ROOT(N) * LogN) = *O(ROOT(N)LogN)
Query is straight forward. Naively count the elements of array A from the extreme which partially overlaps with query range.
For middle O(ROOT(N)) segments do a binary search for k + lazy(segment), in vector list B. Time = O(ROOT(N) * LogN)
Thus each query is answered in O(ROOT(N) * LogN)
For O(Log^2(N)) solution which @glebodin proposed, you can read rachitjain’s answer on this link.
There is also a Log(N) per each query solution explained at the last in that link.