Cartesian Tree
(Algorithm/cartesian.hpp)

• View this file on GitHub
• Last update: 2024-01-12 04:16:01+09:00
• Include: #include "Algorithm/cartesian.hpp"

使い方

vector<int> Cartesian(const vector<int>& a): 数列 $a$ の Cartesian Tree を計算。
それぞれの要素は親の index を表し、根は -1 が入る。

Verified with

• Verify/LC_cartesian_tree.test.cpp

Code

#pragma once

template <typename T> vector<int> Cartesian(const vector<T> &a) {
    const int n = a.size();
    vector<int> res(n, -1);
    int cur;
    rep(i, 1, n) {
        cur = i - 1;
        if (a[cur] > a[i]) {
            int pre = cur;
            while (cur != -1 and a[cur] > a[i])
                pre = cur, cur = res[cur];
            if (cur == -1) {
                res[i] = -1;
                res[pre] = i;
            } else {
                res[i] = cur;
                res[pre] = i;
            }
        } else
            res[i] = cur;
    }
    return res;
}

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

#line 2 "Algorithm/cartesian.hpp"

template <typename T> vector<int> Cartesian(const vector<T> &a) {
    const int n = a.size();
    vector<int> res(n, -1);
    int cur;
    rep(i, 1, n) {
        cur = i - 1;
        if (a[cur] > a[i]) {
            int pre = cur;
            while (cur != -1 and a[cur] > a[i])
                pre = cur, cur = res[cur];
            if (cur == -1) {
                res[i] = -1;
                res[pre] = i;
            } else {
                res[i] = cur;
                res[pre] = i;
            }
        } else
            res[i] = cur;
    }
    return res;
}

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

Back to top page