404Error's blog

Segment tree Related problem?
By 404Error, 9 years ago, In English

Query problems involving calculating GCD or LCM in a range?

How can we solve this kind of problem efficiently? Does any other data structure also helps in solving these kinds of problems? Some hints might be helpful. Even links to blog or papers. Thanks.

  • Vote: I like it
  • -1
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Well, I believe segment tree can handle all associative operations (but some only with point update. As GCD and LCM are associative you can write a simple segment tree and replace your query operation (min/max, sum, ...) with GCD or LCM.

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Sry, u r not wrong, but still segment tree is stronk.

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    But make sure that gcd range update query(like +smth) is possible.

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

    Thanks for replying. I will try to implement it if I do face problems then I will ask you in message.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

BTW I have just started learning segment tree , BIT, Treap and Splay and so was curious to know how it helps so much. For some people its looks stupid question. No need to downvote, If you want to remove it from recent action, then you can tell me i will remove it depending on the request priority.

→ Reply