duckladydinh's blog

Is it possible to implement Fenwick Tree for 2-dimensional query when n, m <= 100000?
By duckladydinh, history, 7 years ago, In English

Hello,

I have been looking for an implementation of 2D Fenwick Tree for n, m<= 100000 without using std::map but with no luck. I want to ask if it is possible to implement 2D Fenwick Tree using O(nlogn) memory and O(logn^2) per update?

Tutorials, ideas or papers, all are very welcome.

Thank you.

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

Comments Comments (21)
| Write comment?
»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Never heard of Fenwick Tree doing that, you may have some luck if you implement is as a tree with pointers and lazy initialization instead of an array. Although in that case segment tree would probably be much easier or at least more popular.

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

    Seriously, you do not know that? It may be even simpler than a segment tree, and it is definitely faster than a segment tree.

    I once wrote a comment explaining this approach.

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

      Doesn't work in online

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        So what?

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it +62 Vote: I do not like it

          Wow, I did not expect such a reaction.

          I mean, did I claim anywhere that this data structure is online? Or was it required in a topic? I meant no offence at all :\

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

        Can someone explain to me what are online and offline queries? Sorry for, maybe, stupid question

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Online means you can process as you read the queries; offline means you read in all the queries and then process them.

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

      Nice and clean trick, thank you.

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

      Thank you. Your comment is very helpful. At least I now know that there is no online version.

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

Yes it is possible.

You can use array of unordered map instead of using map.

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

    I think unordered map will give you Memory Limit Exceeded.

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

      I think it won't give MLE, because it only needs (log N)^2 each query/update

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

    and how can it is O(log^2) per query??? Is unordered map guaranteed to be always O(1)?

    My experience with unordered map is that it is most of the time even slower than normal map, and even if it is sometimes faster, MLE is almost certain

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

    Can someone verify if this is true? I've already tried to solve three problems using unordered/ordered maps instead of a simple array but always got TLE/MLE, is there something else I should bear in mind?

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

I think it can be done using pbds. http://codeforces.net/blog/entry/52094

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

    I solved a problem using the same idea mentioned in the blog. Problem goes like this: You are given a tree on n vertices. And each vertex has a pair ai, bi. Now for each vertex v, you need to count number of it's ancestors u such that av > au and bv > bu. n ≤ 1e5 and ai, bi ≤ 1e9

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

    Thank you, a very nice idea indeed. This is a nice application of pbds

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

You can use a Fenwick of treaps (or any BBST modified to answer range sums) to do that if the queries are online.

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

    I think 2D segment tree lazy may be faster to code, right?

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

      No. You don't need to code anything other than a Fenwick tree if you use this http://codeforces.net/blog/entry/11080. Time might be an issue though. Edit: also, 2D segment tree doesn't work if the queries are online (as far as I know).

      → Reply