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 get`O(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).English statement of 4498 e-olympFirst line contains two numbers — an array size

Nand number of daysD. (1 ≤N,D≤ 10^{6})In second line

Nnumbers — initial array, (|a_{i}| ≤ 10^{9}).Then integer M (1 ≤

M≤ 10^{5}) — number of set-queries. Each query like means that in daydvaluea_{p}will set asv.Then integer K (1 ≤

K≤ 10^{5}) — number of get-queries. Each query like means than you need to find segmentl≤i≤j≤rwith maximal possible sum(empty segment has sum equal 0) at end of dayd, where ,id— identificator of query,z— answer on query with identificatorid- 1, numeration starts from 1.answer[0] = 0,answer is finded sum.Output answers for each query.