mirror of
https://github.com/TheAlgorithms/JavaScript.git
synced 2025-07-05 00:01:37 +08:00
86d333ee94
* chore: Switch to Node 20 + Vitest * chore: migrate to vitest mock functions * chore: code style (switch to prettier) * test: re-enable long-running test Seems the switch to Node 20 and Vitest has vastly improved the code's and / or the test's runtime! see #1193 * chore: code style * chore: fix failing tests * Updated Documentation in README.md * Update contribution guidelines to state usage of Prettier * fix: set prettier printWidth back to 80 * chore: apply updated code style automatically * fix: set prettier line endings to lf again * chore: apply updated code style automatically --------- Co-authored-by: github-actions <${GITHUB_ACTOR}@users.noreply.github.com> Co-authored-by: Lars Müller <34514239+appgurueu@users.noreply.github.com>
98 lines
2.7 KiB
JavaScript
98 lines
2.7 KiB
JavaScript
/**
|
||
* 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 }
|