Querying Our Tree
With the tree built, it's time to extract some information from it!
1// javascript version
2query(v, l, r, ql, qr) {
3 if (ql <= l && r <= qr) {
4 return this.tree[v];
5 }
6 if (qr < l || r < ql) {
7 return 0;
8 }
9 let m = Math.floor((l + r) / 2);
10 return this.query(v*2, l, m, ql, qr) + this.query(v*2+1, m+1, r, ql, qr);
11}Each version of the query function captures the same logic and functionality as your original Python function but in the respective languages.
This function allows you to ask, "Hey tree, can you tell me the sum between indices ql and qr?" And the tree, being the wise entity it is, either provides an answer or divides the task among its children.
Updating: Because Change is the Only Constant
Sometimes, a bread slice gets extra crispy and its rating changes. We need to account for that.
1// javascript version
2update(v, l, r, pos, val) {
3 if (l === r) {
4 this.tree[v] = val;
5 } else {
6 let m = Math.floor((l + r) / 2);
7 if (pos <= m) {
8 this.update(v*2, l, m, pos, val);
9 } else {
10 this.update(v*2+1, m+1, r, pos, val);
11 }
12 this.tree[v] = this.tree[v*2] + this.tree[v*2+1];
13 }
14}With this update method, we locate our slice, adjust its rating, and inform the tree about this delightful crispiness.
A Slice of Action
Let's witness our Segment Tree in action:
1// javascript version
2let ratings = [4, 3, 5, 2, 1];
3let breadTree = new SegmentTree(ratings);
4
5console.log(breadTree.query(1, 0, breadTree.n-1, 1, 3)); // Output: 10 (Because 3 + 5 + 2 = 10)
6breadTree.update(1, 0, breadTree.n-1, 2, 4); // The third slice's rating changed!
7console.log(breadTree.query(1, 0, breadTree.n-1, 1, 3)); // Output: 9 (Because 3 + 4 + 2 = 9)Each version captures the logic and functionality of your original Python code, but in the respective languages.
And there you have it! Your bread slices are now neatly organized in a Segment Tree.
xxxxxxxxxxmain();class SegmentTree { constructor(arr) { this.n = arr.length; this.tree = new Array(4 * this.n).fill(0); this.build(arr, 1, 0, this.n-1); }​ build(arr, v, l, r) { if (l === r) { this.tree[v] = arr[l]; } else { let m = Math.floor((l + r) / 2); this.build(arr, v*2, l, m); this.build(arr, v*2+1, m+1, r); this.tree[v] = this.tree[v*2] + this.tree[v*2+1]; } }​ query(v, l, r, ql, qr) { if (ql <= l && r <= qr) { return this.tree[v]; } if (qr < l || r < ql) { return 0; } let m = Math.floor((l + r) / 2); return this.query(v*2, l, m, ql, qr) + this.query(v*2+1, m+1, r, ql, qr); }​