shakil.ahamed's blog

By shakil.ahamed, history, 7 years ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by shakil.ahamed (previous revision, new revision, compare).

»
7 years ago, # |
Rev. 4   Vote: I like it +8 Vote: I do not like it

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)

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Hi! Can you please explain this in detail? I want to know how this can be done using multiple segment trees

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Feel free to ask what is unclear :)