Penerapan Struktur Data Segment Tree Pada Rancang Algoritma: Studi Kasus URI Online Judge: Rangel And The Array Game II

Perkembangan teknologi informasi dalam beberapa dekade terakhir sangat pesat, terutama dalam hal proses komputasi yang memungkinkan pengambilan keputusan dapat dilakukan dengan cepat dan akurat. Salah satu bidang permasalahan yang menarik untuk dieksplorasi dalam bidang komputasi adalah query processing. Query processing adalah suatu permasalahan untuk memproses beberapa query dari suatu data dengan indeks yang dinamis sesuai dengan kriteria masing-masing query. Tujuan dari query processing adalah menyelesaikan semua query dengan waktu yang efisien dan biaya komputasi yang rendah oleh karena itu diperlukan algoritma yang optimal untuk mencapai hal tersebut. Topik tugas akhir ini mengangkat permasalahan yang terdapat pada situs penilaian daring URI dengan nomor permasalahan 2849 dan judul rangel and the array game II. Pada permasalahan ini diberikan sebuah array bilangan dengan panjang N dan lima bilangan l, r, k, g, d sebanyak Q kali. Bilangan l dan r merepresentasikan indeks batas suatu rentang pencarian dalam array. Pada interval indeks l dan r diminta untuk mencari bilangan terkecil ke-K dan frekuensi bilangan tersebut muncul pada rentang. Pada permasalahan ini memiliki tantangan untuk merancang algoritma yang dapat melakukan pemrosesan tiap case secara optimal pada array yang dinamis karena array yang diproses untuk setiap case berbeda sesuai dengan indeks i dan j. Dengan batasan waktu selama 3 detik, nilai N antara 1 hingga 105 dan jumlah query sampai 105 maka apabila dikerjakan tanpa adanya perencanaan dan perancangan struktur data dan algoritma yang tepat akan menghasilkan status Time Limit Exeeded. Pada tugas akhir ini diimplementasikan struktur data segment tree. Struktur data segment tree digunakan dengan memanfaatkan sifat dari struktur data segment tree, yaitu node parent akan menyimpan representasi nilai dari children nodenya. Hasil dari Tugas Akhir ini diharapkan dapat menjadi acuan dalam pemilihan, desain, dan implementasi struktur data yang tepat untuk memecahkan permasalahan di atas secara optimal dan diharapkan dapat berkontribusi pada perkembangan ilmu pengetahuan dan teknologi informasi kedepannya. ================================================================================================ The development of information technology in recent decades is very rapid, especially in terms of computing processes that enable decision making to be done quickly and accurately. One of the most interesting issues to explore in computing is query processing. Query processing is a problem for processing multiple queries from a data with a dynamic index according to the criteria of each query. The purpose of query processing is to solve all queries with efficient time and low computational cost and therefore an optimal algorithm is needed to achieve this. This final project topic will use a problem in URI online judge website which has 2849 as its problem number and “Rangel and Array Game II” as its title. In this problem, an array of numbers with N length and Q times of five numbers l, r, k, g, d is given. The numbers l and r represent the indices of extreme of thee search interval in the array. On each search interval required to find the Kth smallest number and the frequency of said number in the interval. The challenge of this problem is to design an algorithm that optimally process each query in dynamic array because the said processed array on every case has different i and j extreme. With 3 seconds time limit and the array’s length is up to 105 and the number of queries is also up to 105. Thus, using if the problem is implemented without a well-planned and well-designed algorithm the result certainly is Time Limit Exceeded. This Final Project will be implemented by using segment tree data structure. Segment tree data structure used by utilizing the segment tree’s nature itself, which is every parent node will store representated value of its children. The results of this final project is expected to help determination, design, and implementation process of the correct data structure to optimally solve the problem mentioned above and contribute to development of science and information technology