_QWOiNYUIVMPFSBKLiGSMAP_'s blog

segment tree question
By _QWOiNYUIVMPFSBKLiGSMAP_, history, 6 years ago, In English

IF you have ranges and you want to query on how many elements in this range but every cell have to contain at most one element and the updates are on the range whether be +1 or -1. this could be done with segment tree and how ?

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

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

What is the query supposed to answer?Number of elements in the range?

→ Reply
»
6 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Are you talking about unique elements in range? Also, +-1 on range or on one element?

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

    1- +1/-1 to all the elements in a given range. (update) 2- i am talking about the number of non-zero elements in a given range. (query)

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

      I believe it can't be easily done using a segment tree. Though you can make an sqrt-decomposition of your array where for each block store cnt[] map of elements and a modifier to add to all of them. On update, add +-1 to the modifier for each block that lies entirely inside the range, and manually go through and change all remaining elements (and according cnts). On query, sum cnt[-modifier] for all inside blocks and manually count all remaining elements (not forgetting about their blocks' modifiers). Thus you'll count all zero elements, so subtract it from the range's length to get the count of non-zero

      → Reply