Problem: http://www.spoj.com/problems/IQUERY/
I think we can use segment tree for this problem. I figured out that the multiplication and addition part has the following property:mul(i, j) = mul(i, k)+mul(k+1, j)+mul(i, k)*mul(k+1, j)
where i <= k <= j
.
So, this is easy to do with range trees.
But as bitwise and
is not distributive over addition we can't define the second type of query as the previous one. Anyone approached the problem?
Any hint will be appreciated.