Using persistent data structures for adding range restrictions to searching problems
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 28 (1994) no. 1, pp. 25-49. 
@article{ITA_1994__28_1_25_0,
     author = {Lenhof, Hans-Peter and Smid, Michiel},
     title = {Using persistent data structures for adding range restrictions to searching problems},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {25--49},
     publisher = {EDP-Sciences},
     volume = {28},
     number = {1},
     year = {1994},
     mrnumber = {1271125},
     zbl = {0998.68520},
     language = {en},
     url = {http://www.numdam.org/item/ITA_1994__28_1_25_0/}
}
TY  - JOUR
AU  - Lenhof, Hans-Peter
AU  - Smid, Michiel
TI  - Using persistent data structures for adding range restrictions to searching problems
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1994
SP  - 25
EP  - 49
VL  - 28
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_1994__28_1_25_0/
LA  - en
ID  - ITA_1994__28_1_25_0
ER  - 
%0 Journal Article
%A Lenhof, Hans-Peter
%A Smid, Michiel
%T Using persistent data structures for adding range restrictions to searching problems
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1994
%P 25-49
%V 28
%N 1
%I EDP-Sciences
%U http://www.numdam.org/item/ITA_1994__28_1_25_0/
%G en
%F ITA_1994__28_1_25_0
Lenhof, Hans-Peter; Smid, Michiel. Using persistent data structures for adding range restrictions to searching problems. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 28 (1994) no. 1, pp. 25-49. http://www.numdam.org/item/ITA_1994__28_1_25_0/

1. J. L. Bentley, Decomposable Searching Problems, Inform. Proc. Lett., 1979, 8, 244-251. | MR | Zbl

2. J. L. Bentley, Multidimensional Divide and Conquer, Comm. ACM., 1980, 23, 214-229. | MR | Zbl

3. B. Chazelle and L. J. Guibas, Fractional Cascading I: a Data Structuring Technique, Algorithmica, 1986, 1, 133-162. | MR | Zbl

4. P. F. Dietz and R. Raman, Persistence, Amortization and Randomization, Tech. Report 353, University of Rochester, 1991. | MR

5. M. Dietzfelbinger, A. Karlin, K. Mehlhorn, F. Meyerauf Der Heide, H. Rohnert, R. E. Tarjan, Dynamic Perfect Hashing, Proc. 29-th Annual IEEE Symp. on Foundations of Computer Science, 1988, 524-531.

6. J. R. Driscoll, N. Sarnak, D. D. Sleator and R. E. Tarjan, Making Data Structures Persistent, J. Comput. System Sci., 1989, 38, 86-124. | MR | Zbl

7. H. Edelsbrunner, A Note on Dynamic Range Searching, Bull. of the EATCS, 1981, 15, 34-40.

8. H. N. Gabow, J. L. Bentley and R. E. Tarjan, Scaling and Related Techniques for Geometry Problems, Proc. 16-th Annual ACM Symp. on Theory of Computing, 1984, 135-143.

9. R. Klein, O. Nurmi, T. Ottmann and D. Wood, A Dynamic Fixed Windowing Problem, Algorithmica, 1989, 4, 535-550. | MR | Zbl

10. K. Mehlhorn and S. Näher, Bounded Ordered Dictionaries in O(log log N) Time and O(n) Space, Inform. Proc. Lett., 1990, 35, 183-189. | MR | Zbl

11. M. H. Overmars, The Design of Dynamic Data Structures, Lecture Notes in Computer Science, 1983, Vol. 156, Springer-Verlag, Berlin. | MR | Zbl

12. M. H. Overmars, Efficient Data Structures for Range Searching on a Grid, J. of Algorithms, 1988, 9, 254-275. | MR | Zbl

13. N. Sarnak and R. E. Tarjan, Planar Point Location Using Persistent Search Trees, Comm. A.C.M., 1986, 29, 669-679. | MR

14. H. W. Scholten and M. H. Overmars, General Methods for Adding Range Restrictions to Decomposable Searching Problems, J. Symbolic Computation, 1989, 7, 1-10. | MR | Zbl

15. P. Van Emde Boas, Preserving Order in a Forest in Less than Logarithmic Time and Linear Space, Inform. Proc. Lett., 1977, 6, 80-82. | Zbl

16. P. Van Emde Boas, R. Kaas and E. Zijlstra, Design and Implementation of an Efficient Priority Queue, Math. Systems Theory, 1977, 10, 99-127. | MR | Zbl

17. D. E. Willard and G. S. Lueker, Adding Range Restriction Capability to Dynamic Data Structures, J. A.C.M., 1985, 32, 597-617. | MR | Zbl