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

Commit1a4fe11

Browse files
malfpletrekhleb
authored andcommitted
Added Binary Indexed Tree / Fenwick Tree Implementation (trekhleb#51)
* added fenwick tree implementation* added fenwick tree implementation
1 parenta1060c2 commit1a4fe11

File tree

3 files changed

+94
-0
lines changed

3 files changed

+94
-0
lines changed
Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
exportdefaultclassFenwickTree{
2+
/**
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]
6+
*/
7+
constructor(size){
8+
this.n=size;
9+
this.arr=[];
10+
for(leti=0;i<=size;i+=1)this.arr.push(0);
11+
}
12+
13+
/**
14+
* Adds v to index x
15+
*@param {number} [x]
16+
*@param {number} [v]
17+
*/
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+
}
23+
}
24+
25+
/**
26+
* query sum from index 1 to x
27+
*@param {number} [x]
28+
*@return {number} sum
29+
*/
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];
35+
}
36+
returnret;
37+
}
38+
39+
/**
40+
* query sum from index l to r
41+
*@param {number} [l]
42+
*@param {number} [r]
43+
*@return {number}
44+
*/
45+
queryRange(l,r){
46+
if(l>r)return0;
47+
returnthis.query(r)-this.query(l-1);
48+
}
49+
}
Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
#Binary Indexed Tree / Fenwick Tree
2+
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
4+
5+
This implementation uses the basic range sum query and point update. All the indexes are 1-based
6+
7+
-[Wikipedia](https://en.wikipedia.org/wiki/Fenwick_tree)
8+
-[Geeksforgeeks](https://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/)
Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
importFenwickTreefrom'../FenwickTree';
2+
3+
describe('FenwickTree',()=>{
4+
it('should create empty fenwick tree of correct size',()=>{
5+
consttree1=newFenwickTree(5);
6+
expect(tree1.arr.length).toBe(5+1);
7+
8+
for(leti=0;i<5;i+=1){
9+
expect(tree1.arr[i]).toBe(0);
10+
}
11+
12+
consttree2=newFenwickTree(50);
13+
expect(tree2.arr.length).toBe(50+1);
14+
});
15+
16+
it('should correctly execute queries',()=>{
17+
consttree=newFenwickTree(5);
18+
19+
tree.update(1,4);
20+
tree.update(3,7);
21+
22+
expect(tree.query(1)).toBe(4);
23+
expect(tree.query(3)).toBe(11);
24+
expect(tree.query(5)).toBe(11);
25+
expect(tree.queryRange(2,3)).toBe(7);
26+
27+
tree.update(2,5);
28+
expect(tree.query(5)).toBe(16);
29+
30+
tree.update(1,3);
31+
expect(tree.queryRange(1,1)).toBe(7);
32+
expect(tree.query(5)).toBe(19);
33+
expect(tree.queryRange(1,5)).toBe(19);
34+
35+
expect(tree.queryRange(5,1)).toBe(0);// invalid test
36+
});
37+
});

0 commit comments

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