merge: fixes: #{} (TheAlgorithms#853)

itsmohitmkk · web-flow · commit c3b2bacf0809 · 2021-11-30T18:10:20.000+05:30
* fixes: #{}

* fixes : ISSUE#795

* Fixed ISSUE:795

* Fixed : ISSUE:795

* Fixed ISSUE : 795

* Fixed ISSUE : 795
diff --git a/Trees/FenwickTree.js b/Trees/FenwickTree.js
@@ -0,0 +1,36 @@
+/*
+ * Author: Mohit Kumar
+ * Fedwick Tree Implementation in JavaScript
+ * Fedwick Tree Implementation for finding prefix sum.
+*/
+
+class FenwickTree {
+  constructor (feneickArray, array, n) {
+    for (let i = 1; i <= n; i++) {
+      feneickArray[i] = 0
+    }
+    for (let i = 0; i < n; i++) {
+      this.update(feneickArray, n, i, array[i])
+    }
+  }
+
+  update (feneickArray, n, index, value) {
+    index = index + 1
+    while (index <= n) {
+      feneickArray[index] += value
+      index += index & (-index)
+    }
+  }
+
+  getPrefixSum (feneickArray, index) {
+    let currSum = 0
+    index = index + 1
+    while (index > 0) {
+      currSum += feneickArray[index]
+      index -= index & (-index)
+    }
+
+    return currSum
+  }
+}
+export { FenwickTree }
diff --git a/Trees/test/FenwickTree.test.js b/Trees/test/FenwickTree.test.js
@@ -0,0 +1,22 @@
+import { FenwickTree } from '../FenwickTree'
+
+describe('Fenwick Tree Implementation', () => {
+  const fenwickArray = new Array(1000)
+  const array = [3, 2, 0, 6, 5, -1, 2]
+  const length = array.length
+
+  const fenwickTree = new FenwickTree(fenwickArray, array, length)
+
+  it('Fenwick Tree - Prefix sum of array', () => {
+    const prefixSum = fenwickTree.getPrefixSum(fenwickArray, 6)
+    expect(prefixSum).toBe(23)
+  })
+
+  array[2] += 6
+  fenwickTree.update(fenwickArray, length, 2, 6)
+
+  it('Fenwick Tree - Prefix sum of Updated array', () => {
+    const prefixSum = fenwickTree.getPrefixSum(fenwickArray, 6)
+    expect(prefixSum).toBe(23)
+  })
+})
diff --git a/package-lock.json b/package-lock.json
