|
| 1 | +/** |
| 2 | + * Segment Tree |
| 3 | + * concept : [Wikipedia](https://en.wikipedia.org/wiki/Segment_tree) |
| 4 | + * inspired by : https://www.geeksforgeeks.org/segment-tree-efficient-implementation/ |
| 5 | + * |
| 6 | + * time complexity |
| 7 | + * - init : O(N) |
| 8 | + * - update : O(log(N)) |
| 9 | + * - query : O(log(N)) |
| 10 | + * |
| 11 | + * space complexity : O(N) |
| 12 | + */ |
| 13 | +classSegmentTree{ |
| 14 | +size |
| 15 | +tree |
| 16 | +constructor(arr){ |
| 17 | +// we define tree like this |
| 18 | +// tree[1] : root node of tree |
| 19 | +// tree[i] : i'th node |
| 20 | +// tree[i * 2] : i'th left child |
| 21 | +// tree[i * 2 + 1] : i'th right child |
| 22 | +// and we use bit, shift operation for index |
| 23 | +this.size=arr.length |
| 24 | +this.tree=newArray(2*arr.length) |
| 25 | +this.tree.fill(0) |
| 26 | + |
| 27 | +this.build(arr) |
| 28 | +} |
| 29 | + |
| 30 | +// function to build the tree |
| 31 | +build(arr){ |
| 32 | +const{ size, tree}=this |
| 33 | +// insert leaf nodes in tree |
| 34 | +// leaf nodes will start from index N |
| 35 | +// in this array and will go up to index (2 * N – 1) |
| 36 | +for(leti=0;i<size;i++){ |
| 37 | +tree[size+i]=arr[i] |
| 38 | +} |
| 39 | + |
| 40 | +// build the tree by calculating parents |
| 41 | +// tree's root node will contain all leaf node's sum |
| 42 | +for(leti=size-1;i>0;--i){ |
| 43 | +// current node's value is the sum of left child, right child |
| 44 | +tree[i]=tree[i*2]+tree[i*2+1] |
| 45 | +} |
| 46 | +} |
| 47 | + |
| 48 | +update(index,value){ |
| 49 | +const{ size, tree}=this |
| 50 | + |
| 51 | +// only update values in the parents of the given node being changed. |
| 52 | +// to get the parent move to parent node (index / 2) |
| 53 | + |
| 54 | +// set value at position index |
| 55 | +index+=size |
| 56 | +// tree[index] is leaf node and index's value of array |
| 57 | +tree[index]=value |
| 58 | + |
| 59 | +// move upward and update parents |
| 60 | +for(leti=index;i>1;i>>=1){ |
| 61 | +// i ^ 1 turns (2 * i) to (2 * i + 1) |
| 62 | +// i ^ 1 is second child |
| 63 | +tree[i>>1]=tree[i]+tree[i^1] |
| 64 | +} |
| 65 | +} |
| 66 | + |
| 67 | +// interval [L,R) with left index(L) included and right (R) excluded. |
| 68 | +query(left,right){ |
| 69 | +const{ size, tree}=this |
| 70 | +// cause R is excluded, increase right for convenient |
| 71 | +right++ |
| 72 | +letres=0 |
| 73 | + |
| 74 | +// loop to find the sum in the range |
| 75 | +for(left+=size,right+=size;left<right;left>>=1,right>>=1){ |
| 76 | +// L is the left border of an query interval |
| 77 | + |
| 78 | +// 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. |
| 79 | +// So we will simply include this node to sum and move to the parent of its next node by doing L = (L + 1) / 2. |
| 80 | + |
| 81 | +// if L is even it is the left child of its parent |
| 82 | +// and the interval includes its parent also unless the right borders interfere. |
| 83 | +if((left&1)>0){ |
| 84 | +res+=tree[left++] |
| 85 | +} |
| 86 | + |
| 87 | +// same in R (the right border of an query interval) |
| 88 | +if((right&1)>0){ |
| 89 | +res+=tree[--right] |
| 90 | +} |
| 91 | +} |
| 92 | + |
| 93 | +returnres |
| 94 | +} |
| 95 | +} |
| 96 | + |
| 97 | +export{SegmentTree} |