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

Commit2e5fd8d

Browse files
vignesh-mtrekhleb
authored andcommitted
Segment Tree implementation (trekhleb#45)
* added segment tree implementation - supports custom operation* added readme for segment tree
1 parentbeb8501 commit2e5fd8d

File tree

3 files changed

+294
-0
lines changed

3 files changed

+294
-0
lines changed
Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
#Segment Tree
2+
3+
A segment tree is a data structure designed to perform certain array operations efficiently - especially those involving range queries. A common application is the[Range Minimum Query](https://en.wikipedia.org/wiki/Range_minimum_query) (RMQ) problem, where we are given an array of numbers and need to support operations of updating values of the array and finding the minimum of a contiguous subarray. A segment tree implementation for the RMQ problem takes O(n) to initialize, and O(log n) per query or update. The "minimum" operation can be replaced by any array operation (such as sum).
4+
5+
A segment tree is a binary tree with contiguous subarrays as nodes. The root of the tree represents the whole array. The two children of the root represent the first and second halves of the array. Similarly, the children of each node corresponds to the two halves of the array corresponding to the node. If the array has size n, we can prove that the segment tree has size at most 4n. Each node stores the minimum of its corresponding subarray.
6+
7+
In the implementation, we do not explicity store this tree structure, but represent it using a $4n$ sized array. The left child of node i is 2i and the right child is 2i+1. This is a standard way to represent segment trees, and lends itself to an efficient implementation.
8+
9+
We build the tree bottom up, with the value of each node being the minimum of its children's values. This will take time O(n), with one operation for each node. Updates are also done bottom up, with values being recomputed starting from the leaf, and up to the root. The number of operations done is the height of the tree, which is O(log n) To answer queries, each node splits the query into two parts, one subquery for each child. If a query contains the whole subarray of a node, we can use the precomputed value at the node. Using this optimisation, we can prove that only O(log n) minimum operations are done.
Lines changed: 149 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,149 @@
1+
/**
2+
* Segment Tree implementation for Range Query data structure
3+
* Tracks a array of numbers. 0 indexed
4+
* operation is a binary function (eg sum, min) - needs to be associative
5+
* identity is the identity of the operation
6+
* i.e, operation(x, identity) = x (eg 0 for sum, Infinity for min)
7+
* Supports methods
8+
* update(index, val) - set value of index
9+
* query(l, r) - finds operation(values in range [l, r]) (both inclusive)
10+
*
11+
* As is customary, we store the tree implicitly with i being the parent of 2i, 2i+1.
12+
*/
13+
14+
exportdefaultclassSegmentTree{
15+
/**
16+
* array initialises the numbers
17+
*@param {number[]} array
18+
*/
19+
constructor(array,operation,identity){
20+
this.n=array.length;
21+
this.array=array;
22+
this.tree=newArray(4*this.n);
23+
24+
this.operation=operation;
25+
this.identity=identity;
26+
27+
// use Range Min Query by default
28+
if(this.operation===undefined){
29+
this.operation=Math.min;
30+
this.identity=Infinity;
31+
}
32+
33+
34+
this.build();
35+
}
36+
37+
/**
38+
* Stub for recursive call
39+
*/
40+
build(){
41+
this.buildRec(1,0,this.n-1);
42+
}
43+
44+
/**
45+
* Left child index
46+
*@param {number} root
47+
*/
48+
left(root){
49+
return2*root;
50+
}
51+
52+
/**
53+
* Right child index
54+
*@param {number} root
55+
*/
56+
right(root){
57+
return(2*root)+1;
58+
}
59+
60+
/**
61+
* root is the index in the tree, [l,r] (inclusive) is the current array segment being built
62+
*@param {number} root
63+
*@param {number} l
64+
*@param {number} r
65+
*/
66+
buildRec(root,l,r){
67+
if(l===r){
68+
this.tree[root]=this.array[l];
69+
}else{
70+
constmid=Math.floor((l+r)/2);
71+
// build left and right nodes
72+
this.buildRec(this.left(root),l,mid);
73+
this.buildRec(this.right(root),mid+1,r);
74+
this.tree[root]=this.operation(this.tree[this.left(root)],this.tree[this.right(root)]);
75+
}
76+
}
77+
78+
/**
79+
* Stub for recursive call
80+
*@param {number} lindex
81+
*@param {number} rindex
82+
*/
83+
query(lindex,rindex){
84+
returnthis.queryRec(1,lindex,rindex,0,this.n-1);
85+
}
86+
87+
/**
88+
* [lindex, rindex] is the query region
89+
* [l,r] is the current region being processed
90+
* Guaranteed that [lindex,rindex] contained in [l,r]
91+
*@param {number} root
92+
*@param {number} lindex
93+
*@param {number} rindex
94+
*@param {number} l
95+
*@param {number} r
96+
*/
97+
queryRec(root,lindex,rindex,l,r){
98+
// console.log(root, lindex, rindex, l, r);
99+
if(lindex>rindex){
100+
// happens when mid+1 > r - no segment
101+
returnthis.identity;
102+
}
103+
if(l===lindex&&r===rindex){
104+
// query region matches current region - use tree value
105+
returnthis.tree[root];
106+
}
107+
constmid=Math.floor((l+r)/2);
108+
// get left and right results and combine
109+
constleftResult=this.queryRec(this.left(root),lindex,Math.min(rindex,mid),l,mid);
110+
constrightResult=this.queryRec(
111+
this.right(root),Math.max(mid+1,lindex),rindex,
112+
mid+1,r,
113+
);
114+
returnthis.operation(leftResult,rightResult);
115+
}
116+
117+
/**
118+
* Set array[index] to value
119+
*@param {number} index
120+
*@param {number} value
121+
*/
122+
update(index,value){
123+
this.array[index]=value;
124+
this.updateRec(1,index,value,0,this.n-1);
125+
}
126+
127+
/**
128+
*@param {number} root
129+
*@param {number} index
130+
*@param {number} value
131+
*@param {number} l
132+
*@param {number} r
133+
*/
134+
updateRec(root,index,value,l,r){
135+
if(l===r){
136+
// we are at tree node containing array[index]
137+
this.tree[root]=value;
138+
}else{
139+
constmid=Math.floor((l+r)/2);
140+
// update whichever child index is in, update this.tree[root]
141+
if(index<=mid){
142+
this.updateRec(this.left(root),index,value,l,mid);
143+
}else{
144+
this.updateRec(this.right(root),index,value,mid+1,r);
145+
}
146+
this.tree[root]=this.operation(this.tree[this.left(root)],this.tree[this.right(root)]);
147+
}
148+
}
149+
}
Lines changed: 136 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,136 @@
1+
importSegmentTreefrom'../SegmentTree';
2+
3+
describe('SegmentTree',()=>{
4+
it('create RMQ SegmentTree',()=>{
5+
constarray=[1,2,5,3,4,6,2];
6+
constsegTree=newSegmentTree(array,Math.min,Infinity);
7+
8+
expect(segTree.array.sort()).toEqual(array.sort());
9+
expect(segTree.n).toBe(7);
10+
});
11+
12+
it('check specific tree indices',()=>{
13+
constarray=[1,2,5,3,4,6,2];
14+
constsegTree=newSegmentTree(array,Math.min,Infinity);
15+
16+
// 1 - [0,6]
17+
// 2 - [0,3] 3 - [4,6]
18+
// 4 - [0,1] 5 - [2,3] 6 - [4,5] 7 - [6,6]
19+
// 8 - [0,0] 9 - [1,1] 10 - [2,2] 11 - [3,3] 12 - [4,4] 13 - [5,5]
20+
expect(segTree.tree.slice(8,14)).toEqual(array.slice(0,6));
21+
expect(segTree.tree[7]).toBe(array[6]);
22+
expect(segTree.tree[1]).toBe(Math.min(...array));
23+
expect(segTree.tree[2]).toBe(Math.min(...array.slice(0,4)));
24+
expect(segTree.tree[6]).toBe(Math.min(...array.slice(4,6)));
25+
});
26+
27+
it('check another tree for n=8',()=>{
28+
constarray=[5,4,2,1,4,1,3,1];
29+
constsegTree=newSegmentTree(array,Math.min,Infinity);
30+
31+
// 1 - [0,7]
32+
// 2 - [0,3] 3 - [4,7]
33+
// 4 - [0,1] 5 - [2,3] 6 - [4,5] 7 - [6,7]
34+
// 8 - [0,0] 9 - [1,1] 10 - [2,2] 11 - [3,3] 12 - [4,4] 13 - [5,5] 14 - [6,6] 15 - [7,7]
35+
expect(segTree.tree.slice(8,16)).toEqual(array.slice(0,8));
36+
expect(segTree.tree[7]).toBe(Math.min(...array.slice(6,8)));
37+
expect(segTree.tree[1]).toBe(Math.min(...array));
38+
expect(segTree.tree[2]).toBe(Math.min(...array.slice(0,4)));
39+
expect(segTree.tree[6]).toBe(Math.min(...array.slice(4,6)));
40+
});
41+
42+
it('check query',()=>{
43+
constarray=[1,2,5,3,4,6,2];
44+
constsegTree=newSegmentTree(array,Math.min,Infinity);
45+
46+
consttestRanges=[[0,6],[0,4],[2,6],[3,3],[4,5],[6,6],[1,5],[1,4]];
47+
for(leti=0;i<testRanges.length;i+=1){
48+
constrange=testRanges[i];
49+
expect(segTree.query(range[0],range[1]))
50+
.toBe(Math.min(...array.slice(range[0],range[1]+1)));
51+
}
52+
expect(segTree.query(0,0)).toBe(1);
53+
});
54+
55+
it('check update using queries',()=>{
56+
constarray=[1,2,5,3,4,6,2];
57+
constsegTree=newSegmentTree(array,Math.min,Infinity);
58+
59+
consttestRanges=[[0,6],[0,4],[2,6],[3,3],[4,5],[6,6],[1,5],[1,4]];
60+
61+
expect(segTree.array[0]).toBe(1);
62+
for(leti=0;i<testRanges.length;i+=1){
63+
constrange=testRanges[i];
64+
expect(segTree.query(range[0],range[1]))
65+
.toBe(Math.min(...array.slice(range[0],range[1]+1)));
66+
}
67+
68+
segTree.update(0,3);
69+
array[0]=3;
70+
71+
expect(segTree.array[0]).toBe(3);
72+
for(leti=0;i<testRanges.length;i+=1){
73+
constrange=testRanges[i];
74+
expect(segTree.query(range[0],range[1]))
75+
.toBe(Math.min(...array.slice(range[0],range[1]+1)));
76+
}
77+
78+
segTree.update(2,2);
79+
array[2]=2;
80+
81+
expect(segTree.array[2]).toBe(2);
82+
for(leti=0;i<testRanges.length;i+=1){
83+
constrange=testRanges[i];
84+
expect(segTree.query(range[0],range[1]))
85+
.toBe(Math.min(...array.slice(range[0],range[1]+1)));
86+
}
87+
});
88+
89+
it('check range sum query SegmentTree',()=>{
90+
constarray=[1,2,5,3,4,6,2];
91+
constsum=(a,b)=>a+b;
92+
constsegTree=newSegmentTree(array,sum,0);
93+
94+
consttestRanges=[[0,6],[0,4],[2,6],[3,3],[4,5],[6,6],[1,5],[1,4]];
95+
96+
expect(segTree.array[0]).toBe(1);
97+
for(leti=0;i<testRanges.length;i+=1){
98+
constrange=testRanges[i];
99+
expect(segTree.query(range[0],range[1]))
100+
.toBe(array.slice(range[0],range[1]+1).reduce(sum));
101+
}
102+
103+
segTree.update(0,3);
104+
array[0]=3;
105+
106+
expect(segTree.array[0]).toBe(3);
107+
for(leti=0;i<testRanges.length;i+=1){
108+
constrange=testRanges[i];
109+
expect(segTree.query(range[0],range[1]))
110+
.toBe(array.slice(range[0],range[1]+1).reduce(sum));
111+
}
112+
});
113+
114+
it('check default is rmq',()=>{
115+
constarray=[3,7,2,5,4,3,8,1];
116+
constsegTree=newSegmentTree(array);
117+
118+
consttestRanges=[[0,7],[3,7],[2,5],[4,4]];
119+
120+
for(leti=0;i<testRanges.length;i+=1){
121+
constrange=testRanges[i];
122+
expect(segTree.query(range[0],range[1]))
123+
.toBe(Math.min(...array.slice(range[0],range[1]+1)));
124+
}
125+
126+
segTree.update(0,1);
127+
array[0]=1;
128+
129+
expect(segTree.array[0]).toBe(1);
130+
for(leti=0;i<testRanges.length;i+=1){
131+
constrange=testRanges[i];
132+
expect(segTree.query(range[0],range[1]))
133+
.toBe(Math.min(...array.slice(range[0],range[1]+1)));
134+
}
135+
});
136+
});

0 commit comments

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