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.
↵
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.
