Блог пользователя mehthemez

2D-Segment Tree VS 2D- BIT ?
Автор mehthemez, история, 9 лет назад, По-английски

Hello. I've been doing a problem on poj.com ( link : http://poj.org/problem?id=1195 )

The main idea of the problem is that we are given a S * S grid and there is 2 kind of operations.

Operation 1 : Change the cell x, y by adding a certain value A.

Operation 2 : Answer the sum of the rectangle which is defined by the two points; top leftmost : (l, b), bottom rightmost (r, t)

So obviously we need a 2D Binary Indexed Tree (because of operation 1). But I tried to implement a 2D Segment Tree, and I'm getting a TLE.

Can someone help me figure out why ? Are Segment Trees not efficient here or my implementation of 2D Segment Tree is just bad ?

Link to my C++ code (getting TLE): http://pastebin.com/KA3UXm3N

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

While it's true that a 2D SegTree works, it's pretty much an overkill and it's prone to errors. Plus BITs are slightly faster. BITrees easily scale to higher dimensions by nesting for loops, e.g,:

void BIT_add(int x, int y, int v){
    for(n = x; n < maxn; n += n & -n)
        for(m = y; m < maxm; m += m & -m)
            BIT[n][m] += v;
}

The query follows this same logic. Both query and update have time O( log^d N ) where d is the number of dimensions and N the maximum coordinate. This should be enough for the task you mentioned.

Bear in mind that there are things BITrees can't do and you will inevitably need a 2D SegTree. Take a look at "Game" from IOI 2013 to see what I mean.

Ref: https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/#2d

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Wow, this is really useful! Thanks!

    Whenever I had to do queries like this, I used Quad Trees, but they have O(N) worst time complexity. This is much better.

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Can you show me your implementation of Quad Trees please ? I can't figure out why my implementation is much slower than the 2D-BIT.

      → Ответить
      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        It's supposed to be much slower, like I said above, Quad Trees queries can have as much as 12 * N calls, or something like that, for a N * N table. And BIT's are always logarithmic.

        → Ответить