Skip to content

cartesian_tree.hpp

#include "noya/cartesian_tree.hpp"

View on GitHub

#ifndef NOYA_CARTESIAN_TREE_HPP
#define NOYA_CARTESIAN_TREE_HPP 1

#include <cassert>
#include <vector>

namespace noya {

/// @brief Cartesian tree where each node is the minimum of its subtree. Equal values prefer the leftmost.
struct min_cartesian_tree {
  int n, rt;
  std::vector<int> par, lef, rig;
  template <class T> void build(int n_, T *as) {
    assert(n_ >= 1);
    n = n_;
    rt = 0;
    par.assign(n, -1);
    lef.assign(n, -1);
    rig.assign(n, -1);
    int top = 0;
    std::vector<int> stack(n, 0);
    for (int u = 1; u < n; ++u) {
      if (as[stack[top]] > as[u]) {
        for (; top >= 1 && as[stack[top - 1]] > as[u]; --top) {
        }
        if (top == 0) {
          rt = par[lef[u] = stack[top]] = u;
        } else {
          par[lef[u] = stack[top]] = u;
          rig[par[u] = stack[top - 1]] = u;
        }
        stack[top] = u;
      } else {
        rig[par[u] = stack[top]] = u;
        stack[++top] = u;
      }
    }
  }
  template <class T> void build(const T &as) { build(as.size(), as.data()); }
};

/// @brief Cartesian tree where each node is the maximum of its subtree. Equal values prefer the leftmost.
struct max_cartesian_tree {
  int n, rt;
  std::vector<int> par, lef, rig;
  template <class T> void build(int n_, T *as) {
    assert(n_ >= 1);
    n = n_;
    rt = 0;
    par.assign(n, -1);
    lef.assign(n, -1);
    rig.assign(n, -1);
    int top = 0;
    std::vector<int> stack(n, 0);
    for (int u = 1; u < n; ++u) {
      if (as[stack[top]] < as[u]) {
        for (; top >= 1 && as[stack[top - 1]] < as[u]; --top) {
        }
        if (top == 0) {
          rt = par[lef[u] = stack[top]] = u;
        } else {
          par[lef[u] = stack[top]] = u;
          rig[par[u] = stack[top - 1]] = u;
        }
        stack[top] = u;
      } else {
        rig[par[u] = stack[top]] = u;
        stack[++top] = u;
      }
    }
  }
  template <class T> void build(const T &as) { build(as.size(), as.data()); }
};

} // namespace noya

#endif // NOYA_CARTESIAN_TREE_HPP

#include <cassert>
#include <vector>

namespace noya {

/// @brief Cartesian tree where each node is the minimum of its subtree. Equal values prefer the leftmost.
struct min_cartesian_tree {
  int n, rt;
  std::vector<int> par, lef, rig;
  template <class T> void build(int n_, T *as) {
    assert(n_ >= 1);
    n = n_;
    rt = 0;
    par.assign(n, -1);
    lef.assign(n, -1);
    rig.assign(n, -1);
    int top = 0;
    std::vector<int> stack(n, 0);
    for (int u = 1; u < n; ++u) {
      if (as[stack[top]] > as[u]) {
        for (; top >= 1 && as[stack[top - 1]] > as[u]; --top) {
        }
        if (top == 0) {
          rt = par[lef[u] = stack[top]] = u;
        } else {
          par[lef[u] = stack[top]] = u;
          rig[par[u] = stack[top - 1]] = u;
        }
        stack[top] = u;
      } else {
        rig[par[u] = stack[top]] = u;
        stack[++top] = u;
      }
    }
  }
  template <class T> void build(const T &as) { build(as.size(), as.data()); }
};

/// @brief Cartesian tree where each node is the maximum of its subtree. Equal values prefer the leftmost.
struct max_cartesian_tree {
  int n, rt;
  std::vector<int> par, lef, rig;
  template <class T> void build(int n_, T *as) {
    assert(n_ >= 1);
    n = n_;
    rt = 0;
    par.assign(n, -1);
    lef.assign(n, -1);
    rig.assign(n, -1);
    int top = 0;
    std::vector<int> stack(n, 0);
    for (int u = 1; u < n; ++u) {
      if (as[stack[top]] < as[u]) {
        for (; top >= 1 && as[stack[top - 1]] < as[u]; --top) {
        }
        if (top == 0) {
          rt = par[lef[u] = stack[top]] = u;
        } else {
          par[lef[u] = stack[top]] = u;
          rig[par[u] = stack[top - 1]] = u;
        }
        stack[top] = u;
      } else {
        rig[par[u] = stack[top]] = u;
        stack[++top] = u;
      }
    }
  }
  template <class T> void build(const T &as) { build(as.size(), as.data()); }
};

} // namespace noya