Is there way to solve spoj LITE using BIT?

general
, ,
1

I’m trying to solve [LITE][1] using BIT and it is my


[2]. I've seen comments it can be solved using segment tree, but i'm asking is BIT solution possible?


  [1]: http://www.spoj.com/problems/LITE/
  [2]: http://ideone.com/Ur3a4i
2

I don’t think a standard implementation of a Binary Indexed Tree will solve the problem (in time).

The reason being that the update operation has to be performed over a range instead of on a single location. Time complexity: O(MNlogN)

Lazy propagation with segment trees is the way to go.