データ構造と代数構造 - koba-e964の日記
この記事は、Competitive Programming Advent Calendar 2016 - Adventarの15日目の記事です。 この記事について 去年(2015年)の12月ごろ、「セグメント木が任意のモノイドに対して使えるという(当たり前のことが)明示的に書かれた日本語の記事がないなぁ」と思い、「(当時)来年のAdvent Calendarあたりに書こうか」と思ったので書きました。その後調べてみましたが、どうやらこの1年(2015年12月-2016年12月)で割と書かれたようでした。(この記事の意味とは…) 前述のように多数の記事がこの1年間で出たので、この記事は主にそれらへのリンクを貼り、場合によってコードを紹介することにします。 データ構造と代数構造 セグメント木 <=> モノイド 集合M、Mの要素eとその上の二項演算*があり、*が e * x = x * e = x
データ構造と代数(後編)
この記事はIS17er Advent Calendar 2016の13日目の記事です． 前日の記事データ構造と代数(前編)に対応した後編となっています． Segment tree(つづき) 区間更新，区間畳み込み 最後は区間更新と区間での演算の畳み込みの両方をサポートするタイプです． 例としては，区間に一様に一次関数の作用ができて，かつ区間での最小値も求めたいなどです． 区間での畳み込み単体，区間での更新単体は既に扱ったので，あとはそれらをどううまく組み合わせるかを考えます． 畳み込みを計算するための内部二分木，作用を記録する内部二分木の両方は当然必要で，その2つをうまく同期させなければなりません． 考えねばならないのは，作用を記録する木から畳み込み用の木への影響で， つまり作用クエリが来た時には畳み込み用の木もよしなに(高速に)変更できなければなりません． 例えば，あるノードが対応づいて
データ構造と代数(前編)
この記事はIS17er Advent Calendar 2016の12日目の記事です． この記事では，データ列の連続部分列に対するクエリを扱う基本的なデータ構造についての代数的なお話をします． 具体的には， Segment tree Fenwick tree(Binary indexd tree) Sparse table の3つについて扱います． この並びでお気づきの方もいらっしゃるかもしれませんが，自分がプログラミングコンテストチャンレジブックを読み進めながら思ったことを整理して書き下したものとなっています． 記事の半分以上はこの記事の充実のために新規に学んだものが占めており，素人の学習日記のような側面もあり簡潔さに欠けるので，ぜひデータ構造と代数構造 - koba-e964の日記も読まれることをおすすめします． はじめに 扱うトピックの関係上データ構造はわかるが代数には馴染みがないと
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
The network reliability problem and star semirings
