I tried to test perfomance of different approaches to build and use trie data structure.
I used 706D - Vasiliy's Multiset to test my versions of tries on it.
The question is: Why does approach with pointers takes 2 times more memory than one with static array? As I know, a pointer stores an address of a variable, so it shouldn't take that much memory.
Here are my submissions:
Pointer approach: 40063381
Static array approach: 40063561
Any suggestions are welcomed!
Sorry for my mistakes in English (if there were any)
Storing a pointer takes 4 or 8 bits depending on whether you use 32-bit or 64-bit OS.
Most probably, it is caused by memory fragmentation.
Seems like this is true since his code uses way less memory with custom allocation
40064732
Thank you!
Nice problem, thanks! You can try your trie on this problem, very interesting, but I solved it with sort + implicit trie + binary search in
O(n * log(n) * WORD_WIDTH)time, with your trie you can getO(n * WORD_WIDTH)time.About 64-bits pointers and 32-bit pointers. I think that you can't solve this problem with persistent segment tree if you will use pointers against indexes in array — my friend gets memory limit exceeded, but you can check it and write to me. My solution on array against 64-pointers (russian comments, sorry).
First line contains two numbers — an array size N and number of days D. (1 ≤ N, D ≤ 106)
In second line N numbers — initial array, (|ai| ≤ 109).
Then integer M (1 ≤ M ≤ 105) — number of set-queries. Each query like
means that in day d value ap will set as v.
Then integer K (1 ≤ K ≤ 105) — number of get-queries. Each query like
means than you need to find segment l ≤ i ≤ j ≤ r with maximal possible sum (empty segment has sum equal 0) at end of day d, where 
, id — identificator of query, z — answer on query with identificator id - 1, numeration starts from 1. answer[0] = 0, answer is finded sum.
Output answers for each query.