Aisyah, Nadiah Nuri (2025) Penyelesaian Kasus SPOJ 37921 - Birthday Present Menggunakan Euler Tour, Segment Tree, dan Binary Lifting. Other thesis, Institut Teknologi Sepuluh Nopember.
![[thumbnail of 5025211210-Undergraduate_Thesis.pdf]](http://repository.its.ac.id/style/images/fileicons/text.png) |
Text
5025211210-Undergraduate_Thesis.pdf - Accepted Version Restricted to Repository staff only Download (3MB) | Request a copy |
Abstract
Sphere Online Judge (SPOJ) merupakan salah satu platform pemrograman kompetitif yang menyediakan berbagai permasalahan algoritmik berskala besar. Studi kasus yang diangkat dalam tugas akhir ini adalah SPOJ 37921 – Birthday Present, yang menuntut solusi efisien untuk menangani operasi range update dan point query pada struktur pohon hingga 10⁵ simpul, serta nilai data yang sangat besar, mencapai 10¹⁸. Permasalahan ini dibatasi oleh waktu eksekusi maksimum 1,5 detik dan penggunaan memori sebesar 1536 MB, sehingga memerlukan pendekatan algoritmik yang optimal.
Tugas akhir ini mengintegrasikan tiga teknik utama, yaitu Euler Tour, Segment Tree, dan Binary Lifting. Teknik Euler Tour digunakan untuk merepresentasikan struktur pohon ke dalam bentuk array linear, sehingga operasi terhadap subtree dapat dilakukan sebagai rentang. Segment Tree dimanfaatkan untuk memproses range update dan point query dengan kompleksitas waktu logaritmik, sementara Binary Lifting digunakan untuk mempercepat pencarian ancestor pada jalur antar simpul. Implementasi dilakukan menggunakan bahasa pemrograman C++ dengan pendekatan Segment Tree bottom-up berbasis array.
Hasil pengujian pada SPOJ menunjukkan bahwa solusi yang dikembangkan mampu menyelesaikan seluruh test case dengan waktu rata-rata 0,58 detik dan penggunaan memori sebesar 18,8 MB. Tugas akhir ini membuktikan bahwa integrasi teknik Euler Tour, Segment Tree, dan Binary Lifting efektif dalam menangani permasalahan pada struktur pohon berskala besar.
=========================================================================================================
Sphere Online Judge (SPOJ) is a competitive programming platform that offers a wide range of large-scale algorithmic problems. This undergraduate thesis focuses on the case study SPOJ 37921 – Birthday Present, which requires an efficient solution to manage range update and point query operations on a tree structure containing up to 10⁵ nodes, with data values reaching as large as 10¹⁸. The problem is constrained by a maximum execution time of 1.5 seconds and a memory limit of 1536 MB, thus demanding an optimal algorithmic approach.
This thesis integrates three key techniques: Euler Tour, Segment Tree, and Binary Lifting. The Euler Tour technique is employed to linearize the tree into an array format, allowing subtree operations to be handled as continuous intervals. The Segment Tree is utilized to efficiently perform range updates and point queries with logarithmic time complexity. Meanwhile, Binary Lifting is applied to expedite ancestor queries along paths between nodes. The implementation is developed in C++, using a bottom-up, array-based Segment Tree structure.
Testing on the SPOJ platform demonstrates that the proposed solution successfully passes all test cases, with an average execution time of 0.58 seconds and memory usage of 18.8 MB. This thesis concludes that the integration of Euler Tour, Segment Tree, and Binary Lifting techniques is highly effective for addressing large-scale problems involving tree structures.
| Item Type: | Thesis (Other) |
|---|---|
| Uncontrolled Keywords: | binary lifting, euler tour, pemrograman kompetitif, point query, range update, segment tree, struktur pohon, competitive programming, euler tour, point query, range update, segment tree, tree structure |
| Subjects: | Q Science > QA Mathematics > QA166 Graph theory Q Science > QA Mathematics > QA76.F56 Data structures (Computer science) Q Science > QA Mathematics > QA9.58 Algorithms |
| Divisions: | Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis |
| Depositing User: | Nadiah Nuri Aisyah |
| Date Deposited: | 04 Aug 2025 09:22 |
| Last Modified: | 04 Aug 2025 09:22 |
| URI: | http://repository.its.ac.id/id/eprint/124758 |
Actions (login required)
 |
View Item |