Update Fenwick Tree readme and do code style fixes.

trekhleb · trekhleb · commit 183dade0796c · 2018-06-06T07:41:28.000+03:00
diff --git a/README.md b/README.md
@@ -33,6 +33,7 @@ the data.
     * [AVL Tree](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/tree/avl-tree)
     * [Red-Black Tree](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/tree/red-black-tree)
     * [Segment Tree](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/tree/segment-tree) - with min/max/sum range queries examples
+    * [Fenwick Tree](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/tree/fenwick-tree) (Binary Indexed Tree)
 * [Graph](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/graph) (both directed and undirected)
 * [Disjoint Set](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/disjoint-set)
 
diff --git a/src/data-structures/tree/fenwick-tree/FenwickTree.js b/src/data-structures/tree/fenwick-tree/FenwickTree.js
@@ -1,49 +1,72 @@
 export default class FenwickTree {
   /**
-   * Constructor creates empty fenwick tree of size 'size',
-   *    however, array size is size+1, because index is 1-based
-   * @param  {number} [size]
+   * Constructor creates empty fenwick tree of size 'arraySize',
+   * however, array size is size+1, because index is 1-based.
+   *
+   * @param  {number} arraySize
    */
-  constructor(size) {
-    this.n = size;
-    this.arr = [];
-    for (let i = 0; i <= size; i += 1) this.arr.push(0);
+  constructor(arraySize) {
+    this.arraySize = arraySize;
+
+    // Fill tree array with zeros.
+    this.treeArray = Array(this.arraySize + 1).fill(0);
   }
 
   /**
-   * Adds v to index x
-   * @param  {number} [x]
-   * @param  {number} [v]
+   * Adds value to position.
+   *
+   * @param  {number} position
+   * @param  {number} value
+   * @return {FenwickTree}
    */
-  update(x, v) {
-    if (x < 1 || x > this.n) return;
-    for (let i = x; i <= this.n; i += (i & -i)) {
-      this.arr[i] += v;
+  update(position, value) {
+    if (position < 1 || position > this.arraySize) {
+      throw new Error('Position is out of allowed range');
+    }
+
+    for (let i = position; i <= this.arraySize; i += (i & -i)) {
+      this.treeArray[i] += value;
     }
+
+    return this;
   }
 
   /**
-   * query sum from index 1 to x
-   * @param  {number} [x]
-   * @return {number} sum
+   * Query sum from index 1 to position.
+   *
+   * @param  {number} position
+   * @return {number}
    */
-  query(x) {
-    if (x > this.n) return this.query(this.n);
-    let ret = 0;
-    for (let i = x; i > 0; i -= (i & -i)) {
-      ret += this.arr[i];
+  query(position) {
+    if (position < 1 || position > this.arraySize) {
+      throw new Error('Position is out of allowed range');
     }
-    return ret;
+
+    let sum = 0;
+
+    for (let i = position; i > 0; i -= (i & -i)) {
+      sum += this.treeArray[i];
+    }
+
+    return sum;
   }
 
   /**
-   * query sum from index l to r
-   * @param  {number} [l]
-   * @param  {number} [r]
+   * Query sum from index leftIndex to rightIndex.
+   *
+   * @param  {number} leftIndex
+   * @param  {number} rightIndex
    * @return {number}
    */
-  queryRange(l, r) {
-    if (l > r) return 0;
-    return this.query(r) - this.query(l - 1);
+  queryRange(leftIndex, rightIndex) {
+    if (leftIndex > rightIndex) {
+      throw new Error('Left index can not be greater then right one');
+    }
+
+    if (leftIndex === 1) {
+      return this.query(rightIndex);
+    }
+
+    return this.query(rightIndex) - this.query(leftIndex - 1);
   }
 }
diff --git a/src/data-structures/tree/fenwick-tree/README.md b/src/data-structures/tree/fenwick-tree/README.md
@@ -1,8 +1,18 @@
-# Binary Indexed Tree / Fenwick Tree
+# Fenwick Tree / Binary Indexed Tree
 
-A simple data structure that supports fast range queries in an array. However, it is usually only valid for reversible operations, like addition and subtraction
+A simple data structure that supports fast range queries 
+in an array. However, it is usually only valid for reversible 
+operations, like addition and subtraction
 
-This implementation uses the basic range sum query and point update. All the indexes are 1-based
+Binary Indexed Tree is represented as an array. Each node of Binary Indexed Tree 
+stores sum of some elements of given array. Size of Binary Indexed Tree is equal 
+to `n` where `n` is size of input array. In current implementation we have used 
+size as `n+1` for ease of implementation. All the indexes are 1-based.
+
+![Binary Indexed Tree](https://www.geeksforgeeks.org/wp-content/uploads/BITSum.png)
+
+## References
 
 - [Wikipedia](https://en.wikipedia.org/wiki/Fenwick_tree)
-- [Geeksforgeeks](https://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/)
+- [GeeksForGeeks](https://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/)
+- [YouTube](https://www.youtube.com/watch?v=CWDQJGaN1gY&index=18&t=0s&list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8)
diff --git a/src/data-structures/tree/fenwick-tree/__test__/FenwickTree.test.js b/src/data-structures/tree/fenwick-tree/__test__/FenwickTree.test.js
@@ -3,14 +3,44 @@ import FenwickTree from '../FenwickTree';
 describe('FenwickTree', () => {
   it('should create empty fenwick tree of correct size', () => {
     const tree1 = new FenwickTree(5);
-    expect(tree1.arr.length).toBe(5 + 1);
+    expect(tree1.treeArray.length).toBe(5 + 1);
 
     for (let i = 0; i < 5; i += 1) {
-      expect(tree1.arr[i]).toBe(0);
+      expect(tree1.treeArray[i]).toBe(0);
     }
 
     const tree2 = new FenwickTree(50);
-    expect(tree2.arr.length).toBe(50 + 1);
+    expect(tree2.treeArray.length).toBe(50 + 1);
+  });
+
+  it('should create correct fenwick tree', () => {
+    const inputArray = [3, 2, -1, 6, 5, 4, -3, 3, 7, 2, 3];
+
+    const tree = new FenwickTree(inputArray.length);
+    expect(tree.treeArray.length).toBe(inputArray.length + 1);
+
+    inputArray.forEach((value, index) => {
+      tree.update(index + 1, value);
+    });
+
+    expect(tree.treeArray).toEqual([0, 3, 5, -1, 10, 5, 9, -3, 19, 7, 9, 3]);
+
+    expect(tree.query(1)).toBe(3);
+    expect(tree.query(2)).toBe(5);
+    expect(tree.query(3)).toBe(4);
+    expect(tree.query(4)).toBe(10);
+    expect(tree.query(5)).toBe(15);
+    expect(tree.query(6)).toBe(19);
+    expect(tree.query(7)).toBe(16);
+    expect(tree.query(8)).toBe(19);
+    expect(tree.query(9)).toBe(26);
+    expect(tree.query(10)).toBe(28);
+    expect(tree.query(11)).toBe(31);
+
+    expect(tree.queryRange(1, 1)).toBe(3);
+    expect(tree.queryRange(1, 2)).toBe(5);
+    expect(tree.queryRange(2, 4)).toBe(7);
+    expect(tree.queryRange(6, 9)).toBe(11);
   });
 
   it('should correctly execute queries', () => {
@@ -31,7 +61,35 @@ describe('FenwickTree', () => {
     expect(tree.queryRange(1, 1)).toBe(7);
     expect(tree.query(5)).toBe(19);
     expect(tree.queryRange(1, 5)).toBe(19);
+  });
+
+  it('should throw exceptions', () => {
+    const tree = new FenwickTree(5);
+
+    const updateAtInvalidLowIndex = () => {
+      tree.update(0, 1);
+    };
+
+    const updateAtInvalidHighIndex = () => {
+      tree.update(10, 1);
+    };
+
+    const queryInvalidLowIndex = () => {
+      tree.query(0);
+    };
+
+    const queryInvalidHighIndex = () => {
+      tree.query(10);
+    };
+
+    const rangeQueryInvalidIndex = () => {
+      tree.queryRange(3, 2);
+    };
 
-    expect(tree.queryRange(5, 1)).toBe(0); // invalid test
+    expect(updateAtInvalidLowIndex).toThrowError();
+    expect(updateAtInvalidHighIndex).toThrowError();
+    expect(queryInvalidLowIndex).toThrowError();
+    expect(queryInvalidHighIndex).toThrowError();
+    expect(rangeQueryInvalidIndex).toThrowError();
   });
 });
