presumption's blog

[Query] Persistent Segment Tree and Custom Allocators
By presumption, history, 9 months ago, In English

I was recently up-solving AtCoder Beginner Contest 339 and came across a Persistent Segment Tree Problem G — Smaller Sum.

While implementing my own Persistent Segment Tree. I tried to make it as generic as possible.

Code:

Here are few things that I want your help and opinion on:

  • Is their a more generic and efficient way to implement Persistent Segment Tree? and How to improve the above code?
  • How can you identify if a problem uses Persistent Segment Tree?
  • Is their a better way to implement custom allocator for Competitive Programming(or for C++/C projects)?
  • How to implement Lazy Persistent Segment Tree?
  • How to add documentation to Personal Library codes?

Upd: I re-wrote the Persistent Segment Tree with documentation and without custom allocator. Thanks to lrvideckis and NimaAryan for help.

Code:
  • Vote: I like it
  • +17
  • Vote: I do not like it

»
9 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Implementing an allocator class, I always think about memory alignment. Do you?

→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Not really, I usually use char array for creating a buffers even for TCP/IP stuff.

    → Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

For competitive programming purposes, using an inline static std::deque<node_t> declared inside the class, and a static node_t* new_node() function should be enough (my lazy persistent segment tree template uses it). It has very little overhead compared to the allocator you used, and it's generic and resizable. We use std::deque instead of std::vector because reference invalidation is not an issue in std::deque.

→ Reply
  • »
    »
    9 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I didn't get the deque part, bit of code would help. Can you provide me your implementation of lazy persistent segment tree?

    Upd: Someone helped me understand how to use deque instead of custom allocator. Seem way better then custom allocator.

    → Reply
    • »
      »
      »
      9 months ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      Your new code seems to use vector instead of deque and indices. My point was that you could do something like this:

      // somewhere in the struct
inline static std::deque<Node> node_buffer{};
static Node* new_node() {
  return &node_buffer.emplace_back();
}
// when you need to allocate a new node
Node* x = new_node(); // instead of Node* x = new Node();

      This doesn't work with std::vector since on emplace_back the pointers to the elements in the vector might not remain valid due to potential reallocation of the vector.

      And if you want to give it multiple-constructor-like-syntax, you can do something like this:

      // somewhere in the struct
inline static std::deque<Node> node_buffer{};
template <class... Args>
static Node* new_node(Args&&... args) {
  return &node_buffer.emplace_back(std::forward<Args>(args)...);
}
// when you need to allocate a new node
Node* x = new_node(); // instead of Node* x = new Node();
Node* y = new_node(1); // instead of Node* x = new Node(1);
      → Reply
»
9 months ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

https://github.com/amenotiomoi/template?tab=readme-ov-file#segment-treesingle-point-change-interval-query-persistence

Here's my implementation of the persistent segtree, I've separated the node's merge rules into a new structure, and I'm only using O(1) space in each structure, which means you can use separate persistent segtrees as if they were normal variables, though this causes me to not release memory very well (I don't have a good way to determine the life cycle). It's CP though, memory largely doesn't matter lol

code
→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It might just me but I need my code to reclaim memory before the program termination 👽 . Btw really cool way to document code library on github 👍 but I want to add documentation in code itself.

    → Reply
»
9 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Here is my Persistent Segment Tree without pointers :)

it's more efficient and easier to code.

code
→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have added an updated version of code. Thanks for help.

    → Reply