| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | djm03178 | 152 |
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.
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.
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.
Doesn't work in online
So what?
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 :\
Can someone explain to me what are online and offline queries? Sorry for, maybe, stupid question
Online means you can process as you read the queries; offline means you read in all the queries and then process them.
Thank you so much
Nice and clean trick, thank you.
Thank you. Your comment is very helpful. At least I now know that there is no online version.
Yes it is possible.
You can use array of unordered map instead of using map.
I think unordered map will give you Memory Limit Exceeded.
I think it won't give MLE, because it only needs (log N)^2 each query/update
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
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?
I think it can be done using pbds. http://codeforces.me/blog/entry/52094
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
Thank you, a very nice idea indeed. This is a nice application of pbds
You can use a Fenwick of treaps (or any BBST modified to answer range sums) to do that if the queries are online.
I think 2D segment tree lazy may be faster to code, right?
No. You don't need to code anything other than a Fenwick tree if you use this http://codeforces.me/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).