Cartesian Tree
(tree/cartesian-tree.hpp)

• View this file on GitHub
• Last update: 2023-05-23 20:26:46+09:00
• Include: #include "tree/cartesian-tree.hpp"

Cartesian Tree

概要

数列$(a_n)$が与えられたとき、区間$[0,n)$に対して次の操作を再帰的に繰り返すことで得られる二分木をCartesian Treeと呼ぶ。

• 区間$[l,r)$が与えられたとき、$i \in [l,r)$のうちa_iが最小の$i$(複数ある場合は$i$が最も小さい点)を$m$と置く。
• 頂点$m$を根、区間$[l,m)$から得られる二分木を左の子、区間$[m+1,r)$から得られる二分木を右の子とした木を返す。

Cartesian Treeの構築にかかる時間計算量は直感的には$\mathrm{O}(n \log n)$だが、実はstackを利用することで$\mathrm{O}(n)$での構築が可能である。

Cartesian Treeの長所として「頂点$(u,v)$のLCAが区間$[u,v]$の最小値に対応する」という点があり、前計算$\mathrm{O}(n)$-クエリ$\mathrm{O}(1)$のRMQなどに利用されている。

参考：EXPREP(codechef)　SAを計算して手に入れたLCP配列から構築したCartesian TreeをHLDecしてRSQ+RAQを載せることで解くことが出来る。(想定解はSuffix AutomatonとDSU on TreeとRSQ+RAQらしいが…)

使い方

• CartesianTree(a) : 配列$a$に対して{グラフ,根}を返す。

Depends on

• グラフテンプレート (graph/graph-template.hpp)

Verified with

• verify/verify-aoj-dsl/aoj-dsl-3-d-cartesiantree.test.cpp
• verify/verify-yosupo-graph/yosupo-cartesian.test.cpp

Code

#pragma once

#include <utility>
#include <vector>
using namespace std;

#include "../graph/graph-template.hpp"

// return value : pair<graph, root>
template <typename T>
pair<vector<vector<int>>, int> CartesianTree(vector<T> &a) {
  int N = (int)a.size();
  vector<vector<int>> g(N);
  vector<int> p(N, -1), st;
  st.reserve(N);
  for (int i = 0; i < N; i++) {
    int prv = -1;
    while (!st.empty() && a[i] < a[st.back()]) {
      prv = st.back();
      st.pop_back();
    }
    if (prv != -1) p[prv] = i;
    if (!st.empty()) p[i] = st.back();
    st.push_back(i);
  }
  int root = -1;
  for (int i = 0; i < N; i++) {
    if (p[i] != -1)
      g[p[i]].push_back(i);
    else
      root = i;
  }
  return make_pair(g, root);
}

/**
 * @brief Cartesian Tree
 * @docs docs/tree/cartesian-tree.md
 */

#line 2 "tree/cartesian-tree.hpp"

#include <utility>
#include <vector>
using namespace std;

#line 2 "graph/graph-template.hpp"

template <typename T>
struct edge {
  int src, to;
  T cost;

  edge(int _to, T _cost) : src(-1), to(_to), cost(_cost) {}
  edge(int _src, int _to, T _cost) : src(_src), to(_to), cost(_cost) {}

  edge &operator=(const int &x) {
    to = x;
    return *this;
  }

  operator int() const { return to; }
};
template <typename T>
using Edges = vector<edge<T>>;
template <typename T>
using WeightedGraph = vector<Edges<T>>;
using UnweightedGraph = vector<vector<int>>;

// Input of (Unweighted) Graph
UnweightedGraph graph(int N, int M = -1, bool is_directed = false,
                      bool is_1origin = true) {
  UnweightedGraph g(N);
  if (M == -1) M = N - 1;
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    if (is_1origin) x--, y--;
    g[x].push_back(y);
    if (!is_directed) g[y].push_back(x);
  }
  return g;
}

// Input of Weighted Graph
template <typename T>
WeightedGraph<T> wgraph(int N, int M = -1, bool is_directed = false,
                        bool is_1origin = true) {
  WeightedGraph<T> g(N);
  if (M == -1) M = N - 1;
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    T c;
    cin >> c;
    if (is_1origin) x--, y--;
    g[x].emplace_back(x, y, c);
    if (!is_directed) g[y].emplace_back(y, x, c);
  }
  return g;
}

// Input of Edges
template <typename T>
Edges<T> esgraph(int N, int M, int is_weighted = true, bool is_1origin = true) {
  Edges<T> es;
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    T c;
    if (is_weighted)
      cin >> c;
    else
      c = 1;
    if (is_1origin) x--, y--;
    es.emplace_back(x, y, c);
  }
  return es;
}

// Input of Adjacency Matrix
template <typename T>
vector<vector<T>> adjgraph(int N, int M, T INF, int is_weighted = true,
                           bool is_directed = false, bool is_1origin = true) {
  vector<vector<T>> d(N, vector<T>(N, INF));
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    T c;
    if (is_weighted)
      cin >> c;
    else
      c = 1;
    if (is_1origin) x--, y--;
    d[x][y] = c;
    if (!is_directed) d[y][x] = c;
  }
  return d;
}

/**
 * @brief グラフテンプレート
 * @docs docs/graph/graph-template.md
 */
#line 8 "tree/cartesian-tree.hpp"

// return value : pair<graph, root>
template <typename T>
pair<vector<vector<int>>, int> CartesianTree(vector<T> &a) {
  int N = (int)a.size();
  vector<vector<int>> g(N);
  vector<int> p(N, -1), st;
  st.reserve(N);
  for (int i = 0; i < N; i++) {
    int prv = -1;
    while (!st.empty() && a[i] < a[st.back()]) {
      prv = st.back();
      st.pop_back();
    }
    if (prv != -1) p[prv] = i;
    if (!st.empty()) p[i] = st.back();
    st.push_back(i);
  }
  int root = -1;
  for (int i = 0; i < N; i++) {
    if (p[i] != -1)
      g[p[i]].push_back(i);
    else
      root = i;
  }
  return make_pair(g, root);
}

/**
 * @brief Cartesian Tree
 * @docs docs/tree/cartesian-tree.md
 */

Back to top page