ゆるいプログラミング環境

リューです。
今日は環境構築苦手な僕が、普段(in xx)で使っているプログラミング環境を紹介していこうと思います。

Visual Studio (in Windows)

言わずと知れた超有名IDEです。
非常に多機能で、ソフトウェアを開発するにはもってこいです。
しかしながら、設定がたくさんあり、環境構築が苦手な僕はイマイチ使いこなせていません。

f:id:anctgcc:20141211210728j:plain

結構お高いソフトウェアのようですが、学生はdreamsparkでprofessional版を無償で使用できます。是非使ってみましょう。

Sublime Text (in Linux)

WindowsやMacでも使えるテキストエディタです。
テキストエディタといえばVimやEmacsなどが有名ですが、初期設定ではカーソルの移動がよくわからない設定だったり、Ctrl+Cでコピーできなかったりと、苦労する人や慣れない人も多いのではないしょうか？
sublimeは初期設定でも十分使いやすいので、利用者の手間を煩わせません。ハイライトやインテリジェンス、フォルダごと開いたりなど、プログラミング環境として十分な機能を持ち合わせています。Ctcr+Shift+Bでrunも出来ます。

f:id:anctgcc:20141211212241j:plain

一応シェアウェアのようですが、期限無期限で機能がフルに使える試用版があります。

Ideone.com (in Web)


Ideone.com - Online Compiler and IDE >> C/C++, Java, PHP, Python, Perl and 40+ other compilers and interpreters
Web上で走るIDEです。
プログラミングのためにソフトをダウンロードするのも面倒だ、という人も居るのではないでしょうか？
IdeoneはWebブラウザで動くIDEです。これ以上お手軽なプログラミング環境は無いんじゃないかってぐらいお手軽です。さまざまな言語が使用可能で、使い方は簡単、サイトにアクセスして、コードを書いて、Ideone it!するだけ・・・　かつてこんなに手軽にプログラミングする方法があったでしょうか？
サクッと競技プログラミングしたいときに非常に便利です。僕が一番頻繁に利用しているのがこのIdeoneです。
難点としては、たまにマウスオーバー広告（）が出現したり、サーバーの調子次第で動きが悪くなることがあることです。一応他の環境も用意しておくことをおすすめします。

f:id:anctgcc:20141211213553j:plain

以上が僕が普段使っているプログラミング環境でした。興味があれば試してみてください。
さて、明日の当番はスペードくんにお願いしようと思います。乞うご期待です。

C言語の配列について（超初心者向け）　（はぐめた）９日目

どうも初めまして。はぐめたです。

１年です。初めてのアドベントカレンダーで緊張しまくってますが（というかGCCでやること殆ど初めてばかり）とりあえずよろしくお願いします。

まだプログラミングというものに殆ど触れてない僕は、正直凄いことは全く書けません。
ということで最近授業でやったＣ言語の配列でも紹介します。
凄い口下手なのはご勘弁ください…

配列とは

まず配列というものは、ざっくりいうと同じ型のデータの集まりです。この配列を使うと、同じ型の変数を効率よく扱えるようになります。
例えば…
田中君、中田君、山田君。。。と、１００人の学生がいて、その人たちの成績を管理するとき、一人一人の名前で管理するよりも、番号でやった方が分かり易いですよね。（出席番号もそんな感じ）
それと同じ感じでプログラムでも１００人分全部の変数を作って管理するよりも、学生[0],学生[1],といった感じでまとめて管理した方が分かり易くて、なおかつすっきりします。このまとめたものが配列です。

定義の仕方

普通にint型で定義すると、
int　x;
これで、変数の箱が一つ出来たわけですが、沢山のデータを扱うときには向いてません。
そこで行列を使います。例えば、３つのデータを扱うとすると、
int　x[3]
と書きます。これで、変数の箱が３つ連なってまとめて出来ます。詳しく言うと、
x[0], x[1], x[2]
という箱が出来ます。ここで、この箱たち（例えばx[0]）に数値を入れる時には、
x[0] ＝ １；
と書きます。これで、xの０という箱に１が代入されます。
もし、配列を定義するときに既に入れる数値が決まっているなら、
int x[3] = {1, 2, 3};
という感じで配列と一緒に定義出来ます。この場合、
x[0]には1, x[1]には2, x[2]には3　が入ります。

配列は上のようにして他の言語でも出来ます。
しかし、題にも付いているように、C言語特有の特徴があります。（これは欠点というべき）
それは、配列に配列を丸ごと代入出来ないことです。つまり、箱を１つずつ代入していかなければならないんです。C言語を使うんだったら、こんなミスでエラーを起こさないよう注意してください。


最初はこんなもんかな…よくわからないww
まあテスト終わったことだし、返ってくるテストに怯えつつ僕もまじめにプログラミングの勉強をしようと思います。今度書くときにはこれよりいい記事を書けるよう頑張ります。
次の指名は、「りゅー」先輩でお願いします。

enchant.jsで簡単ブラウザゲーム開発

YuZakuroです。

ANCTGCCではXNAというC#用のフレームワークを主に使用しているということは誰かが書いていたような気がします。

しかし、XNAはすでに開発が停止してしまい、当部は夜更けの迷子的な状態になってしまっています。

現状では、物好きな意欲的な部員は各々で様々なフレームワークを試し、デザイナーなど、多くの人は開発が停止したXNAを未だに使用しています。しかし、VisualStudioのバージョンが(Excelとよく間違えるアイコンの)2010なので、そろそろなんとかしなければいけません。

私が把握している限り、新たなフレームワークを模索している部員とフレームワークは以下のような感じになっています（こんなフレームワーク使ってるのに載ってないよ or 諸事情により載せないでって部員がいたら連絡ください)。

  • YuZakuro - Unity Siv3D UnrialEngine MonoGames
  • rean - Siv3D MonoGames Cocos2d-x
  • reew - Siv3D Cocos2d-x

これを見ると、Siv3Dが人気のようですが、C++のライブラリであるため学習コストが高く、新入生が使いこなせるかが懸案事項です。Cocos2d-xにも同様の問題があり、MonoGamesは日本語のドキュメントが致命的に少ないという問題点があります。

UnityやUnrialEngineなどのゲームエンジンは、私はよく使うのですが、他の人はあまり使わないようです。

というように、どの選択肢も一長一短であり、それ故にXNAが使い続けられてしまっています。

そんななか、現実逃避気味になにかいいフレームワークはないかと探していたところで見つけたのがenchant.jsでした。

概要

enchant.jsはブラウザゲーム用のjavascriptゲームフレームワークです。

ANCTGCCでは主にPC用ゲームを開発していますので、このフレームワークを採用するということはおそらくないですが、少し遊んでみるとなかなか楽しいフレームワークでした。

導入

ダウンロードページからzipファイルをダウンロードします。

解凍すると、中にはライブラリだけでなく、サンプルやリソースも付属しているので、ある程度のプログラミング経験がある方なら簡単なゲームはすぐに作れてしまうのではないでしょうか。

解説

ここまできてYuZakuroは思ったのでした。

「公式のドキュメントが親切すぎる」

公式サイトには日本語で書かれた大量のドキュメント。サンプルには異常なまでに丁寧に書かれた日本語のコメント。

それもそのはず、このライブラリはユビキタスエンターテインメントという日本の会社が開発したものなのです。

ということで、一言。

「公式ドキュメント読んで」

まとめ

非常に雑な説明（というより説明していない）でしたが、公式サイトのドキュメントをよめば、enchant.jsについてはいろいろと知ることができると思います。少しでも興味が湧いた人は、是非試してみてください。

さて、明日はテスト最終日ですね。そんな明日のアドベントカレンダーは期待のホープ、はぐめた君に任せることにしましょう。

スマホでお手軽お絵かき

どうもこんばんわ、クックです。
前のモハくんの紹介では、お絵かきのプロみたいな事言われてましたが、全然そんな事ありません。

さて、今回はプロじゃない僕でもスマホでささっとお絵かきが出来ちゃう、そんな素敵なアプリについて紹介してみたいと思います。

その名も
ibisPaint X
です。

このアプリはiPhone/Android版どちらもあり、アプリストアから無料で入手できます。

まずはどんな感じなのか見てみましょう。

f:id:anctgcc:20141207000328j:plain


広告は表示されてしまいますが、こんな感じです。
そこから[マイ ギャラリー]をタップすると

f:id:anctgcc:20141207000529j:plain


こんな感じで、作品が並んでいますね。(初期状態では何もありませんよ。)

次に、実際にお絵かきをしていきましょう。
[+]ボタンをタップしてキャンバスを追加し、サイズを選んだ後お絵かきスタートです。

f:id:anctgcc:20141207000830j:plain


下には線の形や太さ、消しゴムなどの様々なツールや色を替えるためのパレットなど、豊富なツールがたくさん用意されています。
また、

f:id:anctgcc:20141207001020j:plain

[↓]ボタンをタップすると出てくるのがこのレイヤー管理画面。
ここで新たなレイヤーの追加/削除が行えます。

f:id:anctgcc:20141207001138j:plain

次に、これは選択レイヤーといいます。
このアプリには選択用のブラシで塗った部分のみを着色出来るという機能があります。
これを使えば……

f:id:anctgcc:20141207001529j:plain



f:id:anctgcc:20141207001534j:plain

このように、選択した範囲だけを塗れちゃうんです！

さらに

f:id:anctgcc:20141207001948j:plain

このように、スマホで撮影した写真も取り込めるんです！暇な時描いた線画を黒い線でなぞってこっちで色付け……なんて事も！

以上、簡単ではありますがこのアプリについての説明を終わりたいと思います。
ちょっとでも気になった方は是非、このアプリでお絵かきを始めてみてはいかがでしょうか？

Raspberry Piで簡単お手軽Linux

どうも皆さま、おはこんばんちは。クモハと申します。今日ももう残り少ないですが、僕からはRaspberry Piの紹介をしたいと思います。というのも僕はもともと情報系よりも電気系のあれこれをするのが好きなので、前の4人の情報系のプロ達とはちょっと違う話をします(GCCのアドベントカレンダーのはずなんですが…)。

Raspberry Pi #とは

Raspberry Piは、簡単にいえばLinuxが乗ったちっちゃいコンピュータです。買ってみて驚きました、ほんとに名刺サイズです。こいつにモニターとキーボード・マウスを付けて動くなんて信じられないほどに。しかもちゃんとLAN端子もついてるのでこれだけでパソコンになります。

そして驚くべきことに、このRaspberry Piはとても安い値段で買うことが出来ます。RSコンポーネンツという電子部品等を扱う通販サイトで3940円(僕が購入した時の値段)で買うことが出来ます。



まあこれだけ安いんだから何か短所があるんじゃないかと思うかもしれません。はい、実はCPUクロック周波数が700MHz(オーバークロック可能)、メモリ512MBが最高スペックです。今の時代にしてはもう「低スペ」とされてしまうスペックですが、昔このスペックにウン十万かかっていたことを考えると、まあ納得の行く値段だと思います。



ちなみにRaspberry Piには今の時点で市場に出ているモデルが4つあり、それぞれにA、A+、B、B+という記号が振ってあります。AとBは同じ基板のサイズで、Aが

  • メモリが256MB
  • LAN端子がない
  • USB端子が1個だけ

以外はBと同じです。B+がこの後に、

  • BのUSB端子増設
  • 電源強化
  • ストレージがmicroSDに
  • 基板再設計バージョン

として発売されました。
A+は一番最近に発売されたモデルで、

  • USB端子の数は据え置き
  • 基板のサイズを縮小

したB+のようなものです。


またこのRaspberry Piには「GPIO」という、マイコンで言うI/Oピンのようなものがたくさん生えており、これを使ってLEDチカチカをやったり、モーターを回したりといった制御をすることも出来ます。Raspberry Piを機器に組み込んでLinux上で制御プログラムを書けば、C言語などを使って楽に組み込み機器の開発をすることが出来ます。夢が広がりますね。

これをどう使うか

Raspberry Piをしゃぶり尽くせるかどうかは、今では低スペとなったこの性能とGPIOをどうやって使うかに関わってくると思います。僕はまだGPIOにはあまり手を出してないのですが、スペックの方はシステムリソースを効率よく使うためにCUIで使っています。CUIは難しいと思われがちですが、基本的なコマンドを覚えればそんなに難しくはありません。



ちなみにRaspberry PiをWebサーバーとして使っている人はそこそこいるようで、こいつのもう一つのウリである「低消費電力」という面を十分に活用しています。こいつは電源入力をUSB-microB端子としているので、最大でも5V2Aくらいで動きます。アイドル時はもっと消費電力が少ないですから、常時稼働させるにはもってこいの性能です。



僕の利用ケースを挙げますと、僕はRaspberry Piのためにモニターマウスキーボードを用意できるマネーがなかったのでモニターいらずの方法をとりました。これはネットワーク上に置いたサーバーにログインしてTerminalを直接叩く「SSH接続」というもので(僕も全容を把握してるわけではないのですが)、この方法で家でもインターネット上からでもRaspberry Piにログインしてコマンドを実行することができるようになりました。
今はこのRaspberry PiにRubyとC、C++の開発環境、TeXのコンパイル環境を整備しています。コマンドラインめっちゃ楽しいです。

Raspberry Piと競合するいろいろな製品

こんなRaspberry Piですが、他にもこんな感じの製品はないものかと調べたら、実はいろいろありました。それぞれに一長一短がありますが、個人的にはRaspberry Piが値段とスペックがいい感じに釣り合ってるなぁと感じました。これからこの分野も成長するかもしれませんから、僕も暖かい目で見守っていこうと思います。

最後に

僕は主にコマンドラインで操作していますが、ちゃんとGUIも入っているのでHDMI対応のモニターに繋いでやれば見慣れた雰囲気のデスクトップ画面が出てきますのでご安心を。Webサイトなどを見るとすぐCPU使用率が100%になってしまう可愛い子ですが、是非買って愛してやってください。またこれをきっかけに電気系の制御に興味を持っていただけたら幸いです。

明日はお絵描きさんのクックくんに回します。お絵描きの極意とか教えてもらいましょう。では。

プチコンのススメ

こんばんは。reanです。明日の試験科目の教科書を学校から持って帰るのを忘れました。つらいです。

今日AdventCalendar4日目みたいですが、今までの記事を振り返ってみましょう。

  • ゲームランチャー作ったよ (←わかる)
  • Ruby調べてみたよ (←わからんでもない)
  • BIT！！！BIT！！！ (←！？！？！？？！？！！！！！？？？！！！)

ゲーム創作研究部…一体何者なんだ…

まあ、この話題が逸れまくるのもAdventCalendarの醍醐味なんでしょう、あと21日皆さんで頑張っていくので、読んでいただいている皆さんよろしくお願いいたします。(もう少しゲームの話する人増えないかなあ)

さて、C#でリフレクションして遊ぶゲームのデバッグに生かす話とか、動的アセンブリロードと属性と実行時コード生成と使って色々遊ぶ話とか、Cプリプロセッサーで遊んだ話とか色々迷ったんですが、どれも構想までしかしてなくて全然時間がないので今日はさっくりとした内容でいこうと思います。許して。また時間があるときに回して来て。早めに言って。

皆さん、最近C#書いてますか？ANCTGCCでは、以前から多くの人間がC#とXNAを使ってゲーム開発をしてきました。
XNAは死んでオワコンになってしまいましたが、XNAとほぼ似たAPIでゲーム開発ができる[MonoGame:http://www.monogame.net/]がアツそうですね。
もしくはC++ですか？ [Siv3D:http://play-siv3d.hateblo.jp/]というライブラリがアツそうです。これも要チェックですよね。
いやいや、それともあなたはゲームエンジン派？[Unity5:http://japan.unity3d.com/promo/unity5/]ですか？それとも[UDK:https://www.unrealengine.com/products/udk]？

今日僕はそのどの話もしません。なぜなら...

BASICこそが…時代の最先端だったんだよ！

　　　　　　　　　ナ ゝ　　　ナ ゝ　/　 　 十＿"　 　 ー;=‐　　　　　　　　　|! |!
　　　　　　　　　　cト　　　　cト　/＾､_ﾉ　 | ､.__　つ　 （.__ 　 ￣￣￣￣ 　 ・ ・
ミﾐ:::;,!　　　　　　u　　　　　　　｀ﾞ"~´　　　ヾ彡::l／VvVw、 ,yvヾNヽ　　ゞヾ　 ,.　,.　,.　、､ヾゝヽr＝ヾ
ﾐ::::;/　　￣ﾞ`ｰ-.､　　　　　u　　;,,;　　　j　　 ヾk'!　' l　/ 'ﾚ ^ヽﾍ＼　　 ,rﾞゞﾞ-"､ノ /　l!　!ヽ ､､　|
ミ/　　　　J　　　ﾞ`ｰ､　　　"　;, ;;;　,;;　ﾞ　　u ヾi　　　 ,,./　,　,､ヾヾ　　 | '-- ､..,,ヽ　 j　 !　| Nヾ|
'"　　　　　　　_,,.. -─ゝ.､　　　;, "　;;　　　_,,..._ゞｲ__／/〃 i.! ilヾゞヽ　 | ､　 .r．　ヾ-､;;ﾉ,.:-一'"i
　　j　　　　／　　 ,.- ､　 ヾヽ、　;; ;;　_,-＜　　/／_,,＼' "' !|　:l ﾞi !_,,ヽ.l　`ー─--　 ｴｨ' (． 7 /
　　　　　　:　　　　' ・丿　　￣≠Ξｲ´,-､　ヽ /ｲ´ r．　`ー-'ﾒ ,.-´､　　i　　　　 u　　ヾ｀`ー' ｲ
　　　　　　 ＼_　　　 _,,......::　　　´ﾞi､　`¨　/　i　ヽ.__,,... '　 u ﾞl´.i･j.冫,ｲﾞl　 ／ ｀`-､..-　ノ　:u l
　　　u　　　　　￣￣　　彡"　　　、ヾ￣｀`ﾐ::.l　　u　　　j　　i､｀ー'　.i /　/､._　　　　｀'y　　 /
　　　　　　　　　　　　　　u　　　　　　｀ヽ　　ﾞ:l　　 ,.::- ､,,　,.　ノ　ﾞ u　!　/_　　￣　ー/　u　/
　　　　　　　　　　　_,,..,,_　　　　,.ｨ､　 ／　　　|　 /__　　 ｀`- ､_　　　 l　l　 ｀`ｰt､_　/　　／
　　ﾞ　　　u　　,.／´　"　 ｀`- ､_Ｊ　r'´　 u　丿　.l,...　｀ー一''/　　　ノ　 ﾄ ､,,_____　ﾞ/　／
　　　　　　　 ./＿_　　　　　　　　ｰ７　　　　/、　l　　 'ﾞ　ヽ/　 ,. '"　　＼｀ｰ--- ",.::く､
　　　　　　　/;;;''"　￣￣ ───/　　ﾞ　 ,::'　 ＼ヾﾆ==＝'"／ ｀- ､　　　ﾞー┬ '´　/　＼..,,__
、　　　　　 .i:⌒`─-､_,....　　　　l　　　／　　　　 ｀ー┬一'　　　　　 ヽ　　　 :l　 ／　 , '　｀ソヽ
ヾヽ　　　　 l　　　　　 `　 ｀ヽ、 l　 .／　　ヽ　　　　　 l　　　　　　　　　）　　,; ／　　　,'　　　　'^i

プチコン

皆さん、プチコンというソフトウェアはご存知でしょうか？そうです、DS上でBASICが動くアレです！
そのアレの最新作、http://smileboom.com/special/ptcm3/:プチコン3号がこのまえ発売されました！わー！ぱちぱちぱち！

プチコンをご存知無い方のためにさっくり説明すると、こんな感じです。

  • 3DSでいつでもどこでもBASICが書ける！動く！
  • スプライト機能・BG機能使ってスーパーファミコンを彷彿とさせるようなものが作れる！
  • インターネットを通じて全世界に作品を配信できる
  • たのしい

参考までに、前作で作ったブロック崩しを貼っておきます。こんなかんじのものが作れるよってことで。


プチコンでブロック崩し - YouTube

ぜひみなさん購入して楽しいBASICライフをエンジョイするナウなヤングな若者になりましょう。

そろそろテスト勉強してきます。明日はクモハくんにお願いしたいと思います。

小学生でもわかる累積和と中学生でもわかるBinary Indexed Tree

競技プログラミング

こんばんは、リューです。 今日はテスト３日目でした。留年への新たな一歩を踏み出した気がします。 JOI予選も近いですし、今日は競技プログラミングでたまによく使われるアルゴリズムとデータ構造である累積和とBinary Indexed Tree（通称BIT)の考え方についてのお話をしようと思います。プログラミングを知らない方にも理解できることを目標に書きました。ただし、私の技量では小学生に説明できないので、計算量の詳細や実装のお話はしていません。サンプルコードを追加しました。 その辺の話はググって調べてください。

序章

突然ですがこんな場合を想像してみたください。

あなたはよくA駅やB駅から電車に乗ります。A駅～J駅まであり、行先は様々ですが運賃は駅間ごとに決まっています。

ある日の駅間ごとの運賃は以下の通りでした。

  • A駅～B駅：118円
  • B駅～C駅：191円
  • C駅～D駅：410円
  • D駅～E駅：598円
  • E駅～F駅：129円
  • F駅～G駅：493円
  • G駅～H駅：334円
  • H駅～I駅：357円
  • I駅～J駅：432円

さて、ここで問題です。A駅からG駅まで行くための運賃は何円でしょうか？ また、B駅からI駅まで行くための運賃は何円でしょうか？（コンピュータの気持ちになって計算してみましょう）

.

.

.

.

.

.

計算は終わりましたか？ 答えはA駅からG駅までが1939円、B駅からI駅までが2512円でした。計算する回数が多く少し面倒ですね。1度だけならいいですが何度も計算するとなると少し面倒です。また、これでは駅の数に比例して計算回数が増えるので、駅が1000万駅あると毎回平均約500万回、最悪1000万回計算しないといけません。

累積和

このままでは大変なので、あなたは考えて以下の表を作りました。

  • A駅～B駅： 118円
  • A駅～C駅： 309円
  • A駅～D駅： 719円
  • A駅～E駅：1317円
  • A駅～F駅：1446円
  • A駅～G駅：1939円
  • A駅～H駅：2273円
  • A駅～I駅：2630円
  • A駅～J駅：3062円

この表を使うことで、どこの駅へ行くにもすぐに運賃が求められます。それでだけでなく、B駅からある別の駅に行くにもA駅～B駅までの118円を引くことで1回の計算で運賃が求められます。B駅だけでなく、あらゆる一つの駅からもう一つの駅までの運賃も1回の計算で求めることができます。駅が1000万駅あっても1回だけで計算できます。先ほどより数百万倍速いです。すごいですね。（表を作るのに1000万回計算しないといけませんが）

このようにして、1番目～n番目までの値の総和をそれぞれnで記憶して、区間の値の総和を高速に求めるのが累積和の考え方です。

Binary Indexed Tree

しかし、累積和にもいいことばかりではありません。以下の場合を考えてみましょう。

ある時、電気代の値上げによりA駅～B駅間の運賃が10円値上げしました。1つめの表だとA駅からB駅までの運賃を10円加算すればいいだけですが、累積和の表ではA駅～B駅だけでなく、他の区間の運賃も書き換えないといけません。駅が少ないなら大丈夫かもしれませんが、1000万駅あれば1000万回書き換えです。大変ですね。

ここで登場するのがBinary Indexed Tree、通称BITです。BITは累積和と普通の方法の間を取ったような考え方です。少々奇妙に見えるかもしれませんが、以下の表をご覧ください。（10円はまだ足していません）

  1. A駅～B駅(1駅間)： 118円
  2. A駅～C駅(2駅間)： 309円
  3. C駅～D駅(1駅間)： 410円
  4. A駅～E駅(4駅間)：1317円
  5. E駅～F駅(1駅間)： 129円
  6. E駅～G駅(2駅間)： 622円
  7. G駅～H駅(1駅間)： 334円
  8. A駅～I駅(8駅間)：2691円
  9. I駅～J駅(1駅間)： 432円

A番目の駅からn番目の駅には、2m駅前からn番目の駅までの運賃の総和を記録しています。(mはn/(2m)の余りが０となる最大の自然数)

例えば、1番目のB駅なら20=1で割り切れるので1つ前のA駅からの運賃を記録

4番目のE駅なら22=4で割り切れるので4つ前のA駅からの運賃を記録

6番目のG駅なら21=2で割り切れるので2つ前のE駅からの運賃を記録しています。

n番目までの総和を求める際は、nを二進数に変換し、最も末位の1を0にしながら足していきます。

例えば、7番目のG駅までなら、二進数に変換すると111Bとなり、111B(7)番目のG～H駅と110B(6)番目のE～G駅と100B(4)番目のA～E駅を足して求めることができます。

9番目のJ駅までなら、二進数に変化すると1001Bとなり、1001B(9)番目のI～J駅と1000B(8)番目のA～I駅を足して求めることができます。

12/3追記　divさんに図解していただきました。ご提供ありがとうございました！。

図解

また、累積和と同様に引き算をすることで、あらゆる一つの駅からもう一つの駅までの運賃も簡単に求めることができます。

駅の数が少ないとむしろ効率が悪いように感じるかもしれませんが、BITなら駅が1000万駅に増えても加算、区間の総和の計算ともに約20回で計算できます。（表を作るには累積和などよりも少し多めに計算しないといけません）

このように、加算、区間の総和の計算ともにそこそこ優秀なのがBITの強みです。

さいごに

みなさん、累積和とBITについて理解いただけましたでしょうか？駄文で申し訳ありませんでしたが、少しでも累積和とBITを理解いただけたら幸いです。

明日、12/4のアドベントカレンダーはreanさんに書いてもらおうと思います。元会長のすばらしい記事に乞うご期待です。

サンプルソース

//累積和
#include <iostream>
using namespace std;
const int SIZE=1<<10;
int array[SIZE+1];
int cumsum[SIZE+1];//今回の実装では0番目は番兵にしています。
//番兵にしなくてもいいのですが、個人的にはこちらの方が直観的で書きやすいと思います。
int sum(int a,int b){//array[a]~array[b]までの総和を求めます
    if(a>=b)
        return 0;
    return cumsum[b]-cumsum[a-1];
}
void add(int a,int x){//一応加算できますが、O(n)と重く、加算するときはBITを使うのでたいてい書きません。
    for(int i=a;i<=SIZE;++i)
        cumsum[i]+=x;
}
int main() {
    for(int i=1;i<=SIZE;++i)//適当に配列を作ります
        array[i]=i;
    
    for(int i=1;i<=SIZE;++i)//累積和を求めていきます
        cumsum[i]=cumsum[i-1]+array[i];
    
    // your code goes here
    return 0;
}

//BIT
#include <iostream>
using namespace std;
const int SIZE=1<<10;//サイズは2の乗数じゃなくても構いません
int array[SIZE+1];
int BIT[SIZE+1];//0番目を番兵にしています
int sum(int a){
    int ans=0;
    while(a){
        ans+=BIT[a];
        int least=a&-a;//これで最も末位の1のビットを求めることができます。
        a-=least;
    }
    return ans;
}
int sum(int a,int b){//array[a]~array[b]までの総和を求めます
    if(a>b)
        return 0;
    return sum(b)-sum(a-1);
}
void add(int a,int x){//加算の方法は本文では説明しませんでした。最も末位の1のビットを繰り上げながら加算していきます。
    while(a<=SIZE){
        BIT[a]+=x;
        int least=a&-a;//sumのleastど同様
        a+=least;//leastの桁を繰り上げます。
    }
}
int main() {
    for(int i=1;i<=SIZE;++i)//適当に配列を作ります
        array[i]=i;
    
    for(int i=1;i<=SIZE;++i)//BITを求めていきます
        add(i,array[i]);
    // your code goes here
    return 0;
}

追記

12/3 Binary Indexed TreeがBinary Index Treeになっていたのを修正

同日 サンプルソースを追加 提供していただいた画像を追加 12/13 BITのサンプルソースが間違っていたのを修正