Commit0b8bc8d

authored

Update segment_tree.md

1 parente4b572c commit0b8bc8dCopy full SHA for 0b8bc8d

File tree

-5

lines changed

-5

lines changed

Lines changed: 4 additions & 5 deletions

Original file line number	Diff line number	Diff line change
`@@ -387,18 +387,17 @@ Instead, we can use the same idea as in the previous sections, and find the posi`
`387`	`387`	`by moving each time to the left or the right, depending on the maximum value of the left child.`
`388`	`388`	`Thus finding the answer in $O(\log n)$ time.`
`389`	`389`
`390`		`-An example of using the following code would be get_first(1,0,n-1,5,8,14) since our segment tree starts at node 1. This would request a value greater than 14 between $[5,8]$.`
`391`	`390`	```{.cpp file=segment_tree_first_greater}
`392`		`-int get_first(int v, int tl, int tr, int l, int r, intgreater_than) {`
	`391`	`+int get_first(int v, int tl, int tr, int l, int r, intx) {`
`393`	`392`	`if(tl > r \|\| tr < l) return -1;`
`394`		`- if(t[v] <=greater_than) return -1;`
	`393`	`+ if(t[v] <=x) return -1;`
`395`	`394`
`396`	`395`	`if (tl== tr) return tl;`
`397`	`396`
`398`	`397`	`int tm = tl + (tr-tl)/2;`
`399`		`- int left = get_first(2*v, tl, tm, l, r,greater_than);`
	`398`	`+ int left = get_first(2*v, tl, tm, l, r,x);`
`400`	`399`	`if(left != -1) return left;`
`401`		`- return get_first(2*v+1, tm+1, tr, l ,r,greater_than);`
	`400`	`+ return get_first(2*v+1, tm+1, tr, l ,r,x);`
`402`	`401`	`}`
`403`	`402`	```
`404`	`403`

Comments

(0)