mohamedeltair's blog

By mohamedeltair, history, 6 years ago, In English

As the title says, there are these two types of queries. number of values (n) <= 100000 and number of queries <= 200000, the solution that came to my mind is using a segment tree, where each node of the segment tree is an AVL tree that stores the elements of the segment tree node interval in ascending order, and each node of any AVL tree will store the sum of elements of the subtree rooted at this node.

So if I need to update an element (write a new value to it), I go to the segment tree nodes whose intervals contain the position of the element (log(n) nodes) and update the AVL tree of each of these nodes (each update is log(n)), so in total (log(n))^2.

And if I want sum of numbers less than x in interval l to r, I do a query operation so that when the segment tree node is totally inside l to r, I use the AVL tree of this node to get sum of elements less than x in log(n) complexity, and the higher level segment tree nodes will return the summation of these lower level segment tree nodes' sums (so in total (log(n))^2).

If number of queries/updates is Q, their complexity becomes Q*(log(n))^2. am I walking in the right path or is there something wrong in this approach ?

  • Vote: I like it
  • +3
  • Vote: I do not like it

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

Compressed segment tree, counting points (ai, i) in the rectangle [0, x] × [l, r]. Complexity per update/query. It was used in several problems, mainly IOI'13 Game.

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

    Would you please provide a good link for this?

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

      It's an IOI problem ffs, can't you look it up yourself? Here

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

        I mean a link for compressed segment tree.

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

          Same link. Last problem, Game. It uses a compressed segment tree. The code should be there too.

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

If the problem is already available in an OJ, could you please share the link?