TL;DR セグメント木とは, ある半開区間の圏表現$\mathbb{I}$から何らかの圏$C$への関手$F$である. セグメント木の一点・多点更新クエリとは自然変換である. セグメント木という呼称はあくまで関手の計算グラフのとり方によるものであって, Sparse Table等の(列を計算するための)手法も, 基本的には統一した観点で見ることができる. はじめに 本記事は「高速計算可能な区間クエリとはどのようなものか」へと圏論的なモデルを与える. 特にセグメント木にフォーカスしているが, [2]における議論を前提とするならば, 本記事の内容はSparse Tableや累積和にも一般化可能であ…