Cacher is the code snippet organizer for pro developers

//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|
---------------------------------