データ構造と代数(後編)

この記事はIS17er Advent Calendar 2016の13日目の記事です. 前日の記事データ構造と代数(前編)に対応した後編となっているので,まずはそちらをお読み下さい.


Read more

Share Comments

データ構造と代数(前編)

この記事はIS17er Advent Calendar 2016の12日目の記事です.

この記事では,列とその連続部分列に対するクエリを扱う基本的なデータ構造についての代数的なお話をします.具体的には,Segment Tree, Binary Indexd TreeとSparse Tableを扱います.この並びでお気づきの方もいらっしゃるとは思いますが,要は僕がプログラミングコンテストチャンレジブックを読み進めながら思ったことをまとめた記事になっています.

そもそもこの記事を書くまで知らなかったようなデータ構造についても扱っており,素人の学習日記のような側面もあり簡潔さに欠けるので,是非データ構造と代数構造 - koba-e964の日記も読まれることをおすすめします(ちなみに,Advent CalendarのタイトルのIS17erとは東京大学理学部情報科学科2017年度進学生のことを指すのですが,こちらの記事は学科の先輩が書かれたものです).

ブログ自体書くのがはじめてで,どんな方に読んで頂いてるのかよく分からないので念のための注意(言い訳)ですが,僕はプログラミング自体大学で初めて触れたド素人なので,競技プログラミング系の記事と言い切ってしまうとその手の人が期待する水準には恐らく及びません(今は友人にICPCに誘われて慌てて上の本で勉強中です),が,代数的に汎用的だが高速に動作するC++コードも目玉の一つなので,是非斜め読みしていってください.

全体は前編と後編からなり,この記事は 前編 です.


Read more

Share Comments