5,337
edits
Data Structures: Difference between revisions
→Segment Trees
| Line 68: | Line 68: | ||
* This is a binary tree for holding segments.<br> | * This is a binary tree for holding segments.<br> | ||
* Leaves hold something called "elementary intervals" and internal nodes hold the union of elementary intervals of its children. | * Leaves hold something called "elementary intervals" and internal nodes hold the union of elementary intervals of its children. | ||
* In addition, each leaf or node v also holds intervals which span their segment, i.e. <math>{X \ | * In addition, each leaf or node v also holds intervals which span their segment, i.e. <math>\{X \mid Int(v) \in X\}</math> | ||
==Spatial Data Structures== | ==Spatial Data Structures== | ||