@@ -0,0 +1,33 @@
+# クラス FenwickTree
+- - -
+
+長さ $N$ の long型配列に対し,
+
+* 要素の1点変更
+* 区間の要素の総和
+
+を $O(\log N)$ の時間で求めることができるデータ構造です.
+
+
+## コンストラクタ
+### FenwickTree
+```java
+public FenwickTree(int n)
+```
+
+長さ $n$ の配列 $a_0, a_1, \dots, a_{n-1}$を作ります. 初期値はすべて0です.
+計算量: $O(n)$
+
+## メソッド
+### add
+```java
+public void add(int p, long x)
+```
+配列の第$p$要素に$x$を加える. すなわち, `a[p] += x` のこと.
+計算量: $O(\log N)$
+
+### sum
+```java
+public long sum(int l, int r)
+```
+$a_l + a_{l+1} + \dots + a_{r-1}$の値を返す. 計算量: $O(\log n)$