3 ms·
The common solution is to hold size of subtree in the nodes in addition to the value a.k.a treap with implicit keys.
by kilotaras 7y ago
The common solution is to hold size of subtree in the nodes in addition to the value a.k.a treap with implicit keys.
- foobarqwertz 7y agoI propose a challenge: Provide the interface for the datastructure and the test tool.
- pornel 7y agoBut at this point you're adding even more bookkeeping and implementation complexity just to use a data structure that's not ideal in the first place (for performance, sequential memory layout is better than chasing pointers).