セグ木 デバッグ用関数付き
//SegmentTree(セグ木)
template <class T>
class SegmentTree {
private:
T init_val;
std::vector<T> ary;
std::function<T(T, T)> func;
public:
SegmentTree(int n, T val, std::function<T(T, T)> f) : init_val(val), func(f) {
ary.resize(static_cast<int>(std::pow(2, std::ceil(std::log(n) / std::log(2)) + 1) - 1), val);
}
void init(int n, T val, std::function<T(T, T)> f) {
ary.resize(static_cast<int>(std::pow(2, std::ceil(1.0*std::log(n) / std::log(2)) + 1) - 1), val);
init_val = val;
func = f;
}
void update(int i, T val) {
i += ary.size() / 2;
ary[i] = val;
while (i > 0) {
i = (i - 1) / 2;
ary[i] = func(ary[2 * i + 1], ary[2 * i + 2]);
}
}
// 区間[a, b)のfuncの返す値を返す (query_(a, b, 0, 0, n)と呼び出す)
T query_(int a, int b, int i, int l, int r) {
if (r <= a || b <= l) return init_val;
if (a <= l && r <= b) return ary[i];
else {
T vl = query_(a, b, 2 * i + 1, l, (l + r) / 2);
T vr = query_(a, b, 2 * i + 2, (l + r) / 2, r);
return func(vl, vr);
}
}
// 上限(b)は少し大きめに取るべし
T query(int a, int b) {
return query_(a, b, 0, 0, ary.size() / 2 + 1);
}
T operator[](int i) {
return query(i, i + 1);
}
void debug_show() {
for (int i = ary.size() / 2; i < ary.size(); ++i) {
std::cerr << ary[i] << " ";
}
std::cout << "\n";
}
void debug_show_all() {
std::vector<std::string> s(ary.size());
std::vector<int> len(ary.size(), 0);
for (int i = 0; i < ary.size(); ++i) {
if (ary[i] <= -INFINT) s[i] = "-INF";
else if (ary[i] >= INFINT) s[i] = "INF";
else s[i] = std::to_string(ary[i]);
}
int lenSum = 1;
for (int i = ary.size() / 2; i < ary.size(); ++i) {
len[i] = s[i].size();
lenSum += len[i] + 1;
}
for (int i = ary.size() - 1; i > 0; --i) {
len[(i - 1) / 2] += len[i] + (i % 2);
}
bool startF = true;
int tmpSum = 0;
std::cerr << std::string(lenSum, '-') << " ~ segment-tree debug\n";
for (int i = 0; i < ary.size(); ++i) {
if (startF) {
std::cerr << "|";
startF = false;
tmpSum = 1;
}
int space = len[i] - s[i].size();
std::cerr << std::string(space / 2, ' ') << s[i] << std::string((space + 1) / 2, ' ');
tmpSum += len[i] + 1;
if (tmpSum >= lenSum) {
std::cerr << "|\n";
startF = true;
}
else {
std::cerr << "|";
}
}
std::cerr << std::string(lenSum, '-') << "\n";
}
};
// 使用例(データの大きさnとする)
// SegmentTree<int> st(n, INFLL, [](int l, int r){return std::min(l, r);}); //最小値
// SegmentTree<int> st(n, -INFLL, [](int l, int r){return std::max(l, r);}); //最大値
// SegmentTree<int> st(n, 0, [](int l, int r){return l+r;}); //合計
15
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9
--------------------------------- ~ segment-tree debug
| 77 |
| 31 | 46 |
| 9 | 22 | 21 | 25 |
| 4 | 5 |14 | 8 | 8 |13 |16 | 9 |
|3|1|4|1|5|9|2|6|5|3|5|8|9|7|9|0|
---------------------------------