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.

Auto comment: topic has been updated by silentboy302 (previous revision, new revision, compare).let's look for each bit separately. then i-th bit is contained in (2^(number of elements in the segment that have 1 in that bit) — 1 subsets)

so you need to keep log segment trees (in i-th segment tree you contain b[j] = (a[j] >> i) & 1, and then answer is sum(2^i*(2^sum(i-th segment tree, l, r) — 1)

Thanks. It was easy to verify that it should works.

I will think at bit level from the next time if I stuck in any bit-wise issue.