Skip to content

fixes: #{} #853

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
raklaptudirm merged 6 commits into from
Nov 30, 2021
Merged

fixes: #{} #853

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
6 commits
Select commit Hold shift + click to select a range
f7d2498
fixes: #{}
itsmohitmkk Nov 27, 2021
06f1527
fixes : ISSUE#795
itsmohitmkk Nov 27, 2021
8b4c1d9
Fixed ISSUE:795
itsmohitmkk Nov 28, 2021
c90bc22
Fixed : ISSUE:795
itsmohitmkk Nov 29, 2021
1de5b36
Fixed ISSUE : 795
itsmohitmkk Nov 30, 2021
871401a
Fixed ISSUE : 795
itsmohitmkk Nov 30, 2021
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
36 changes: 36 additions & 0 deletions Trees/FenwickTree.js
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -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 }
22 changes: 22 additions & 0 deletions Trees/test/FenwickTree.test.js
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -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)
})
})
Loading