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.