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

Автор duckladydinh, история, 7 лет назад, По-английски

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.

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

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

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.

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

Yes it is possible.

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

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

    I think unordered map will give you Memory Limit Exceeded.

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

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

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

    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

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

    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?

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

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

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

    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

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

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

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

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