vEB tree based on CLRS 3rd edition

main.cpp

#include "veb.hpp"
#include <iostream>

int main() {
  std::cin.tie(nullptr)->sync_with_stdio(false);

  assert((1 << 18 > 200'001));

  int q;
  std::cin >> q;

  int height[200'001];
  auto tree = VebTree(18);

  while (q--) {
    int x;
    std::cin >> x;

    auto x_height = 0;

    if (auto y = tree.successor(x)) {
      x_height = height[*y] + 1;
    }
    if (auto y = tree.predecessor(x)) {
      x_height = std::max(x_height, height[*y] + 1);
    }

    height[x] = x_height;
    tree.insert(x);
    std::cout << x_height << '\n';
  }
}

veb.hpp

#pragma once

#include <cstdint>
#include <optional>

using i64 = int64_t;
using usize = size_t;
using isize = ssize_t;

namespace veb {
struct Node {
private:
  i64 key_len;

  isize min, max;

  Node *children;
  Node *summary;

public:
  Node(i64 key_len) : key_len(key_len), min(1 << key_len), max(-1) {
    if (key_len > 1) {
      children = static_cast<Node *>(
          ::operator new[]((1 << (key_len / 2)) * sizeof(Node)));
      for (size_t i = 0; i < 1 << (key_len / 2); i++)
        new (&children[i]) Node((key_len + 1) / 2);
      summary = new Node(key_len / 2);
    } else {
      children = summary = nullptr;
    }
  }

  Node() = delete;
  Node(const Node &) = delete;
  Node(Node &&) = delete;
  auto operator=(const Node &) = delete;
  auto operator=(Node &&) = delete;

  ~Node() {
    if (key_len > 1) {
      for (size_t i = 0; i < 1 << (key_len / 2); i++)
        children[i].~Node();
      ::operator delete[](children);
      delete summary;
    }
  }

  constexpr auto size() const noexcept -> usize { return 1 << key_len; }

  constexpr auto minimum() const noexcept -> std::optional<usize> {
    if (empty())
      return std::nullopt;
    else
      return {min};
  }

  constexpr auto maximum() const noexcept -> std::optional<usize> {
    if (empty())
      return std::nullopt;
    else
      return {max};
  }

  constexpr auto empty() const noexcept -> bool { return max == -1; }

  constexpr auto member(usize idx) const noexcept -> bool {
    if (idx == min || idx == max)
      return true;
    if (key_len == 1)
      return false;

    return children[high(idx)].member(low(idx));
  }

  constexpr auto successor(usize idx) const noexcept -> std::optional<usize> {
    if (key_len == 1)
      if (idx == 0 && max == 1)
        return {1};
      else
        return std::nullopt;
    else if (!empty() && idx < min)
      return {min};

    if (auto max_low = children[high(idx)].maximum())
      if (low(idx) < *max_low) {
        auto offset = *children[high(idx)].successor(low(idx));
        return {(high(idx) << hkl()) | offset};
      }

    if (auto succ_cluster = summary->successor(high(idx))) {
      auto offset = *children[*succ_cluster].minimum();
      return {(*succ_cluster << hkl()) | offset};
    }

    return std::nullopt;
  }

  constexpr auto predecessor(usize idx) const noexcept -> std::optional<usize> {
    if (key_len == 1)
      if (idx == 1 && min == 0)
        return {0};
      else
        return std::nullopt;
    else if (!empty() && idx > max)
      return {max};

    if (auto min_low = children[high(idx)].minimum())
      if (low(idx) > *min_low) {
        auto offset = *children[high(idx)].predecessor(low(idx));
        return {(high(idx) << hkl()) | offset};
      }

    if (auto pred_cluster = summary->predecessor(high(idx))) {
      auto offset = *children[*pred_cluster].maximum();
      return {(*pred_cluster << hkl()) | offset};
    }

    if (!empty() && idx > min)
      return {min};

    return std::nullopt;
  }

  constexpr auto insert(usize idx) noexcept -> void {
    if (!member(idx))
      insert_unsafe(idx);
  }

  constexpr auto insert_unsafe(usize idx) noexcept -> void {
    auto idxi = isize(idx);
    if (empty()) {
      min = max = idxi;
      return;
    }

    if (idxi < min)
      std::swap(idxi, min);

    if (key_len > 1) {
      if (children[high(idxi)].empty())
        summary->insert_unsafe(high(idxi));
      // note: constant-time if above if statement runs
      children[high(idxi)].insert_unsafe(low(idxi));
    }

    if (idxi > max)
      max = idxi;
  }

private:
  constexpr inline auto high(usize idx) const noexcept -> usize {
    return idx >> hkl();
  }
  constexpr inline auto low(usize idx) const noexcept -> usize {
    return idx & ((1 << hkl()) - 1);
  }
  constexpr inline auto hkl() const noexcept -> usize {
    return (key_len + 1) / 2;
  }
};
}; // namespace veb

using VebTree = veb::Node;