You should read about Segment Tree. This blog relly helped me to understand it — segment tree!

there are great tutorial on russian: tutorial, you can translate it with any translator.

There is a variant of BIT Trees that does range_update & point_query we will use this one

To update a range [l, r] with value V (incrementing every element in range by V), we add V to bit[l] and subtract it from bit[r + 1], since bit tree returns for we always get the right results for point queries

Now in order to make range_queries and range_updates, lets have a look at our array a:

[0, 0, 0, 0, 0, 0]

Calling update(l = 3, r = 5, v = 5) should make it like this:

[0, 0, 5, 5, 5, 0]

And prefix_sum array: [0, 0, 5, 10, 15, 15]

Let's divide the array into 3 parts:

a[1, ..., l - 1] query(x) should return 0

a[l, ..., r] query(x) should return V × (x - (l - 1)) = Vx - V(l - 1)

a[r + 1, ..., N] query(x) should return V × (r - (l - 1)) = Vr - V(l - 1)

So basically, query(x) is now like a linear function of index x: f(x) = Ax + B

The terms that depend on x can be stored in a bit tree and other terms in another bit tree

Pseudo_code:

update_point(bit, x, v):
  while(x <= N):  
    bit[x] += v    
    x += x&-x



update_range(l, r, v):
  update_point(bitAX, l, v)  
  update_point(bitAX, r+1, -v)  
  update_point(bitB, l, -v * (l-1))  
  update_point(bitB, r+1, v * r)



query_point(bit, x)
  sum = 0
  while(x > 0): 
    sum += bit[x]    
    x += x&-x
    


query(x):
  return x * query_point(bitAX, x) + query_point(bitB, x)
  


query(l, r):
  return query(r) + query(l-1)

Read this Blog : Various Usage Of BIT