データ構造と代数(前編)
この記事はIS17er Advent Calendar 2016の12日目の記事です． この記事では，データ列の連続部分列に対するクエリを扱う基本的なデータ構造についての代数的なお話をします． 具体的には， Segment tree Fenwick tree(Binary indexd tree) Sparse table の3つについて扱います． この並びでお気づきの方もいらっしゃるかもしれませんが，自分がプログラミングコンテストチャンレジブックを読み進めながら思ったことを整理して書き下したものとなっています． 記事の半分以上はこの記事の充実のために新規に学んだものが占めており，素人の学習日記のような側面もあり簡潔さに欠けるので，ぜひデータ構造と代数構造 - koba-e964の日記も読まれることをおすすめします． はじめに 扱うトピックの関係上データ構造はわかるが代数には馴染みがないと
初心者の初心者による初心者のための典型segment tree - DEGwerのブログ
§0.はじめに この記事は、Competitive Programming Advent Calendar Div2013の11日目の記事として書かれたものです。この記事では、列に対して変な操作をして変なクエリがくる系の問題のsegment treeによる解法を説明します。 また、「初心者の初心者による初心者のための」と銘打っていますが、 segment treeとはどういうものか知っている 遅延更新のやり方が分かっている の2点を仮定します。前者が分からない人は蟻本、後者が分からない人はkyuridenamidaさんのこの記事(http://d.hatena.ne.jp/kyuridenamida/20121114/1352835261)を見てください。 §1.segment treeとは何か まずsegment treeが何ができるデータ構造なのかを示します。segment treeと
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
