Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit183dade

Browse files
committed
Update Fenwick Tree readme and do code style fixes.
1 parent1a4fe11 commit183dade

File tree

4 files changed

+129
-37
lines changed

4 files changed

+129
-37
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -33,6 +33,7 @@ the data.
3333
*[AVL Tree](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/tree/avl-tree)
3434
*[Red-Black Tree](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/tree/red-black-tree)
3535
*[Segment Tree](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/tree/segment-tree) - with min/max/sum range queries examples
36+
*[Fenwick Tree](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/tree/fenwick-tree) (Binary Indexed Tree)
3637
*[Graph](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/graph) (both directed and undirected)
3738
*[Disjoint Set](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/disjoint-set)
3839

Lines changed: 52 additions & 29 deletions
Original file line numberDiff line numberDiff line change
@@ -1,49 +1,72 @@
11
exportdefaultclassFenwickTree{
22
/**
3-
* Constructor creates empty fenwick tree of size 'size',
4-
* however, array size is size+1, because index is 1-based
5-
*@param {number} [size]
3+
* Constructor creates empty fenwick tree of size 'arraySize',
4+
* however, array size is size+1, because index is 1-based.
5+
*
6+
*@param {number} arraySize
67
*/
7-
constructor(size){
8-
this.n=size;
9-
this.arr=[];
10-
for(leti=0;i<=size;i+=1)this.arr.push(0);
8+
constructor(arraySize){
9+
this.arraySize=arraySize;
10+
11+
// Fill tree array with zeros.
12+
this.treeArray=Array(this.arraySize+1).fill(0);
1113
}
1214

1315
/**
14-
* Adds v to index x
15-
*@param {number} [x]
16-
*@param {number} [v]
16+
* Adds value to position.
17+
*
18+
*@param {number} position
19+
*@param {number} value
20+
*@return {FenwickTree}
1721
*/
18-
update(x,v){
19-
if(x<1||x>this.n)return;
20-
for(leti=x;i<=this.n;i+=(i&-i)){
21-
this.arr[i]+=v;
22+
update(position,value){
23+
if(position<1||position>this.arraySize){
24+
thrownewError('Position is out of allowed range');
25+
}
26+
27+
for(leti=position;i<=this.arraySize;i+=(i&-i)){
28+
this.treeArray[i]+=value;
2229
}
30+
31+
returnthis;
2332
}
2433

2534
/**
26-
* query sum from index 1 to x
27-
*@param {number} [x]
28-
*@return {number} sum
35+
* Query sum from index 1 to position.
36+
*
37+
*@param {number} position
38+
*@return {number}
2939
*/
30-
query(x){
31-
if(x>this.n)returnthis.query(this.n);
32-
letret=0;
33-
for(leti=x;i>0;i-=(i&-i)){
34-
ret+=this.arr[i];
40+
query(position){
41+
if(position<1||position>this.arraySize){
42+
thrownewError('Position is out of allowed range');
3543
}
36-
returnret;
44+
45+
letsum=0;
46+
47+
for(leti=position;i>0;i-=(i&-i)){
48+
sum+=this.treeArray[i];
49+
}
50+
51+
returnsum;
3752
}
3853

3954
/**
40-
* query sum from index l to r
41-
*@param {number} [l]
42-
*@param {number} [r]
55+
* Query sum from index leftIndex to rightIndex.
56+
*
57+
*@param {number} leftIndex
58+
*@param {number} rightIndex
4359
*@return {number}
4460
*/
45-
queryRange(l,r){
46-
if(l>r)return0;
47-
returnthis.query(r)-this.query(l-1);
61+
queryRange(leftIndex,rightIndex){
62+
if(leftIndex>rightIndex){
63+
thrownewError('Left index can not be greater then right one');
64+
}
65+
66+
if(leftIndex===1){
67+
returnthis.query(rightIndex);
68+
}
69+
70+
returnthis.query(rightIndex)-this.query(leftIndex-1);
4871
}
4972
}
Lines changed: 14 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,18 @@
1-
#Binary IndexedTree /Fenwick Tree
1+
#FenwickTree /Binary Indexed Tree
22

3-
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
3+
A simple data structure that supports fast range queries
4+
in an array. However, it is usually only valid for reversible
5+
operations, like addition and subtraction
46

5-
This implementation uses the basic range sum query and point update. All the indexes are 1-based
7+
Binary Indexed Tree is represented as an array. Each node of Binary Indexed Tree
8+
stores sum of some elements of given array. Size of Binary Indexed Tree is equal
9+
to`n` where`n` is size of input array. In current implementation we have used
10+
size as`n+1` for ease of implementation. All the indexes are 1-based.
11+
12+
![Binary Indexed Tree](https://www.geeksforgeeks.org/wp-content/uploads/BITSum.png)
13+
14+
##References
615

716
-[Wikipedia](https://en.wikipedia.org/wiki/Fenwick_tree)
8-
-[Geeksforgeeks](https://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/)
17+
-[GeeksForGeeks](https://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/)
18+
-[YouTube](https://www.youtube.com/watch?v=CWDQJGaN1gY&index=18&t=0s&list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8)

‎src/data-structures/tree/fenwick-tree/__test__/FenwickTree.test.js

Lines changed: 62 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -3,14 +3,44 @@ import FenwickTree from '../FenwickTree';
33
describe('FenwickTree',()=>{
44
it('should create empty fenwick tree of correct size',()=>{
55
consttree1=newFenwickTree(5);
6-
expect(tree1.arr.length).toBe(5+1);
6+
expect(tree1.treeArray.length).toBe(5+1);
77

88
for(leti=0;i<5;i+=1){
9-
expect(tree1.arr[i]).toBe(0);
9+
expect(tree1.treeArray[i]).toBe(0);
1010
}
1111

1212
consttree2=newFenwickTree(50);
13-
expect(tree2.arr.length).toBe(50+1);
13+
expect(tree2.treeArray.length).toBe(50+1);
14+
});
15+
16+
it('should create correct fenwick tree',()=>{
17+
constinputArray=[3,2,-1,6,5,4,-3,3,7,2,3];
18+
19+
consttree=newFenwickTree(inputArray.length);
20+
expect(tree.treeArray.length).toBe(inputArray.length+1);
21+
22+
inputArray.forEach((value,index)=>{
23+
tree.update(index+1,value);
24+
});
25+
26+
expect(tree.treeArray).toEqual([0,3,5,-1,10,5,9,-3,19,7,9,3]);
27+
28+
expect(tree.query(1)).toBe(3);
29+
expect(tree.query(2)).toBe(5);
30+
expect(tree.query(3)).toBe(4);
31+
expect(tree.query(4)).toBe(10);
32+
expect(tree.query(5)).toBe(15);
33+
expect(tree.query(6)).toBe(19);
34+
expect(tree.query(7)).toBe(16);
35+
expect(tree.query(8)).toBe(19);
36+
expect(tree.query(9)).toBe(26);
37+
expect(tree.query(10)).toBe(28);
38+
expect(tree.query(11)).toBe(31);
39+
40+
expect(tree.queryRange(1,1)).toBe(3);
41+
expect(tree.queryRange(1,2)).toBe(5);
42+
expect(tree.queryRange(2,4)).toBe(7);
43+
expect(tree.queryRange(6,9)).toBe(11);
1444
});
1545

1646
it('should correctly execute queries',()=>{
@@ -31,7 +61,35 @@ describe('FenwickTree', () => {
3161
expect(tree.queryRange(1,1)).toBe(7);
3262
expect(tree.query(5)).toBe(19);
3363
expect(tree.queryRange(1,5)).toBe(19);
64+
});
65+
66+
it('should throw exceptions',()=>{
67+
consttree=newFenwickTree(5);
68+
69+
constupdateAtInvalidLowIndex=()=>{
70+
tree.update(0,1);
71+
};
72+
73+
constupdateAtInvalidHighIndex=()=>{
74+
tree.update(10,1);
75+
};
76+
77+
constqueryInvalidLowIndex=()=>{
78+
tree.query(0);
79+
};
80+
81+
constqueryInvalidHighIndex=()=>{
82+
tree.query(10);
83+
};
84+
85+
constrangeQueryInvalidIndex=()=>{
86+
tree.queryRange(3,2);
87+
};
3488

35-
expect(tree.queryRange(5,1)).toBe(0);// invalid test
89+
expect(updateAtInvalidLowIndex).toThrowError();
90+
expect(updateAtInvalidHighIndex).toThrowError();
91+
expect(queryInvalidLowIndex).toThrowError();
92+
expect(queryInvalidHighIndex).toThrowError();
93+
expect(rangeQueryInvalidIndex).toThrowError();
3694
});
3795
});

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp