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
```

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
```

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.