Блог пользователя presumption

[Query] Persistent Segment Tree and Custom Allocators
Автор presumption, история, 9 месяцев назад, По-английски

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:
  • Проголосовать: нравится
  • +17
  • Проголосовать: не нравится

»
9 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

→ Ответить
»
9 месяцев назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    9 месяцев назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      9 месяцев назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

      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);
      → Ответить
»
9 месяцев назад, # |
← Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

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
→ Ответить
  • »
    »
    9 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
»
9 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Here is my Persistent Segment Tree without pointers :)

it's more efficient and easier to code.

code
→ Ответить