JavaScript/Trees/FenwickTree.js at master · Guduly/JavaScript · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/*
 * Author: Mohit Kumar
 * Fenwick Tree Implementation in JavaScript
 * Fenwick Tree Implementation for finding prefix sum.
*/

classFenwickTree{
constructor(feneickArray,array,n){
for(leti=1;i<=n;i++){
feneickArray[i]=0
}
for(leti=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){
letcurrSum=0
index=index+1
while(index>0){
currSum+=feneickArray[index]
index-=index&(-index)
}

returncurrSum
}
}
export{FenwickTree}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/*
 * Author: Mohit Kumar
 * Fenwick Tree Implementation in JavaScript
 * Fenwick Tree Implementation for finding prefix sum.
*/

classFenwickTree{
constructor(feneickArray,array,n){
for(leti=1;i<=n;i++){
feneickArray[i]=0
}
for(leti=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){
letcurrSum=0
index=index+1
while(index>0){
currSum+=feneickArray[index]
index-=index&(-index)
}

returncurrSum
}
}
export{FenwickTree}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/*
 * Author: Mohit Kumar
 * Fenwick Tree Implementation in JavaScript
 * Fenwick Tree Implementation for finding prefix sum.
*/

classFenwickTree{
constructor(feneickArray,array,n){
for(leti=1;i<=n;i++){
feneickArray[i]=0
}
for(leti=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){
letcurrSum=0
index=index+1
while(index>0){
currSum+=feneickArray[index]
index-=index&(-index)
}

returncurrSum
}
}
export{FenwickTree}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/*
 * Author: Mohit Kumar
 * Fenwick Tree Implementation in JavaScript
 * Fenwick Tree Implementation for finding prefix sum.
*/

classFenwickTree{
constructor(feneickArray,array,n){
for(leti=1;i<=n;i++){
feneickArray[i]=0
}
for(leti=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){
letcurrSum=0
index=index+1
while(index>0){
currSum+=feneickArray[index]
index-=index&(-index)
}

returncurrSum
}
}
export{FenwickTree}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/*
 * Author: Mohit Kumar
 * Fenwick Tree Implementation in JavaScript
 * Fenwick Tree Implementation for finding prefix sum.
*/

classFenwickTree{
constructor(feneickArray,array,n){
for(leti=1;i<=n;i++){
feneickArray[i]=0
}
for(leti=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){
letcurrSum=0
index=index+1
while(index>0){
currSum+=feneickArray[index]
index-=index&(-index)
}

returncurrSum
}
}
export{FenwickTree}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/*
 * Author: Mohit Kumar
 * Fenwick Tree Implementation in JavaScript
 * Fenwick Tree Implementation for finding prefix sum.
*/

classFenwickTree{
constructor(feneickArray,array,n){
for(leti=1;i<=n;i++){
feneickArray[i]=0
}
for(leti=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){
letcurrSum=0
index=index+1
while(index>0){
currSum+=feneickArray[index]
index-=index&(-index)
}

returncurrSum
}
}
export{FenwickTree}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/*
 * Author: Mohit Kumar
 * Fenwick Tree Implementation in JavaScript
 * Fenwick Tree Implementation for finding prefix sum.
*/

classFenwickTree{
constructor(feneickArray,array,n){
for(leti=1;i<=n;i++){
feneickArray[i]=0
}
for(leti=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){
letcurrSum=0
index=index+1
while(index>0){
currSum+=feneickArray[index]
index-=index&(-index)
}

returncurrSum
}
}
export{FenwickTree}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/*
 * Author: Mohit Kumar
 * Fenwick Tree Implementation in JavaScript
 * Fenwick Tree Implementation for finding prefix sum.
*/

classFenwickTree{
constructor(feneickArray,array,n){
for(leti=1;i<=n;i++){
feneickArray[i]=0
}
for(leti=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){
letcurrSum=0
index=index+1
while(index>0){
currSum+=feneickArray[index]
index-=index&(-index)
}

returncurrSum
}
}
export{FenwickTree}