これを作るに至った動機

平衡二分探索木を実装したい！
でもいきなり作るにはハードルが高い...
そうだ！自己参照構造体でセグ木を書いて練習しよう！
自己参照構造体で書くセグ木は、他にも発展性が高いらしいので一石二鳥！
（これが書けるようになると、必要なところだけ作るセグ木や、永続セグ木などをすっとかけるようになると赤コーダーの人がツイートしていた）
※始めに断っておくとこのセグ木は再帰で書いているため遅く、あまり実用的ではありません。

そもそも自己参照構造体とは

メンバに自分自身と同じ型の構造体へのポインタを持つ構造体のこと

struct hoge{
    hoge* next; //二分木だとポインタが二つになる
};

めっちゃ簡略化するとこんな感じ
std::listや大体の二分探索木がこれ

実装

C++での実装を乗せます。
折角なので軽く解説します。

constexpr long long LINF = 4611686015206162431;
int op(int x, int y) {
    return min(x, y);
}
int e() {
    return LINF;
}
namespace Library {
    template<class T>class slow_segment_tree {
        struct node {
            T sum = e();
            node* child[2];
        };
        node* root = NULL; //根ノード
        int depth = 0; //セグ木の深さ
        void make_node(node*& np, int d) {
            np = new node;
            if (d > 0) {
                make_node(np->child[0], d - 1);
                make_node(np->child[1], d - 1);
            }
            return;
        }
        void set_all(node*& np, int pos, int d, vector<int>& v) {
            np = new node;
            if (d == -1) {
                if (pos < v.size())np->sum = v[pos];
                return;
            }
            set_all(np->child[0], pos, d - 1, v);
            set_all(np->child[1], pos + (1 << d), d - 1, v);
            np->sum = op(np->child[0]->sum, np->child[1]->sum);
            return;
        }
        void set_sub(node* np, int pos, T n, int p) {//ノード 変更する位置 変更後の数値 深さ
            if (p == -1) {
                np->sum = n;
                return;
            }
            set_sub(np->child[(bool)(pos & (1 << p))], pos, n, p - 1);
            np->sum = op(np->child[0]->sum, np->child[1]->sum);
        }
        T prod_sub(node* np, int l, int r, int a, int b) {//今いるノード, ノードの範囲[l, r), 欲しい範囲[a, b)
            if (r <= a || b <= l) {
                return e();
            }else if (a <= l && r <= b) {
                return np->sum;
            }else {
                return op(prod_sub(np->child[0], l, (l + r) / 2, a, b), prod_sub(np->child[1], (l + r) / 2, r, a, b));
            }
        }
    public:
        slow_segment_tree(int size) {
            assert(size > 0);
            while ((1U << depth) < (unsigned int)(size)) depth++;
            make_node(root, depth);
        }
        slow_segment_tree(vector<int>& v) {
            int size = v.size();
            assert(size > 0);
            while ((1U << depth) < (unsigned int)(size)) depth++;
            set_all(root, 0, depth - 1, v);
        }
        void set(int pos, T n) {//pos番目をnにする
            assert(pos < (1 << depth));
            set_sub(root, pos, n, depth - 1);
        }
        T get(int pos) {//pos番目を返す
            assert(pos < (1 << depth));
            node* n = root;
            for (int d = depth - 1; d >= 0; d--) {
                n = n->child((bool)(pos & (1 << d)));
            }
            return n->sum;
        }
        T all() {
            return root->sum;
        }
        T prod(int l, int r) {// [l, r) の和
            assert(l < (1 << depth) && r <= (1 << depth));
            if (r <= l) {
                return e();
            }
            return prod_sub(root, 0, 1 << depth, l, r);
        }
    };
}

抽象化セグ木なので二項演算(op)と単位元(e)を変えることで、様々な機能を持たせることができます。
上ではrange max queryです。

コンストラクタ

コンストラクタは、深さを持たせてdfsしながらノードを作っていきます。
rootをNULLで初期化することで簡潔に実装出来ます。

値の取得

深さをfor文で回し、npを更新します。
左右どちらのノードに進むか判定するためにbit演算を使っています。
これは非再帰で書くことができました。

値の更新

深さを持たせ再帰します。
左右どちらのノードに進むか判定するためにbit演算を使っています。
葉まで行ったら値を書き換え、帰りがけに更新します。
非再帰で書くのは厳しそうでした。

最小値の取得

親から子へとたどっていき、区間に収まるものを見つけます。これは普通のトップダウン型セグ木とあまり変わりません。
またこれもボトムアップで非再帰にするのは厳しそうでした。

速さ

AOJのRMQの問題でACLのセグ木と比較しました。
ACLのセグ木⇒0.02s
自己参照構造体で作るセグ木⇒0.04s
このセグ木はどうしても再帰で書くことが多くなるため、速さを出すことができず、速いとは言えません。

aspirator’s blog

自己参照構造体でセグ木を書く