Repository navigation
Expand file tree
/
Copy pathSegmentTree.js
More file actions
97 lines (83 loc) · 2.73 KB
/
Copy pathSegmentTree.js
File metadata and controls
97 lines (83 loc) · 2.73 KB
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
/**
* Segment Tree
* concept : [Wikipedia](https://en.wikipedia.org/wiki/Segment_tree)
* inspired by : https://www.geeksforgeeks.org/segment-tree-efficient-implementation/
*
* time complexity
* - init : O(N)
* - update : O(log(N))
* - query : O(log(N))
*
* space complexity : O(N)
*/
class SegmentTree {
size
tree
constructor(arr) {
// we define tree like this
// tree[1] : root node of tree
// tree[i] : i'th node
// tree[i * 2] : i'th left child
// tree[i * 2 + 1] : i'th right child
// and we use bit, shift operation for index
this.size = arr.length
this.tree = new Array(2 * arr.length)
this.tree.fill(0)
this.build(arr)
}
// function to build the tree
build(arr) {
const { size, tree } = this
// insert leaf nodes in tree
// leaf nodes will start from index N
// in this array and will go up to index (2 * N – 1)
for (let i = 0; i < size; i++) {
tree[size + i] = arr[i]
}
// build the tree by calculating parents
// tree's root node will contain all leaf node's sum
for (let i = size - 1; i > 0; --i) {
// current node's value is the sum of left child, right child
tree[i] = tree[i * 2] + tree[i * 2 + 1]
}
}
update(index, value) {
const { size, tree } = this
// only update values in the parents of the given node being changed.
// to get the parent move to parent node (index / 2)
// set value at position index
index += size
// tree[index] is leaf node and index's value of array
tree[index] = value
// move upward and update parents
for (let i = index; i > 1; i >>= 1) {
// i ^ 1 turns (2 * i) to (2 * i + 1)
// i ^ 1 is second child
tree[i >> 1] = tree[i] + tree[i ^ 1]
}
}
// interval [L, R) with left index(L) included and right (R) excluded.
query(left, right) {
const { size, tree } = this
// cause R is excluded, increase right for convenient
right++
let res = 0
// loop to find the sum in the range
for (left += size, right += size; left < right; left >>= 1, right >>= 1) {
// L is the left border of an query interval
// if L is odd it means that it is the right child of its parent and our interval includes only L and not the parent.
// So we will simply include this node to sum and move to the parent of its next node by doing L = (L + 1) / 2.
// if L is even it is the left child of its parent
// and the interval includes its parent also unless the right borders interfere.
if ((left & 1) > 0) {
res += tree[left++]
}
// same in R (the right border of an query interval)
if ((right & 1) > 0) {
res += tree[--right]
}
}
return res
}
}
export { SegmentTree }