Goで型を挿げ替え可能なデータ構造ライブラリを作る - QiitaGo Advent Calendar 2015 その2 の 11日目の記事です。 Go Advent Calendar 2015 の本日の記事 → Golangで画像をglitchできるライブラリの紹介 Go Advent Calendar 2015 その3 の本日の記事 → Goのインタフェースがパフォーマンスに及ぼす影響 最近Goで書かれたアルゴリズムとデータ構造のライブラリを読み漁っていて、型と振る舞いを挿げ替えできるライブラリを作る方法を学んだのでノウハウを記事にしました。今回は題材として点更新＋区間参照のシンプルなセグメントツリーを扱います。 まずセグメントツリーの概要を述べ、愚直な実装を示した後にそれを汎用化します。 セグメントツリーとは 数値が格納された配列をイメージしてください。配列は、単一要素に定数時間でアクセスでき、参照／更新のコストは共に $O(1)$ です。 しかし
