DCP-602: Quad Tree Back to All Problems

Beginner Beginners Problems > Implementation


Suppose you are given a two dimensional **N * N** (for a pretty large **N**, large enough to be not handled by brute-force) grid of integer value and you’re asked to perform operations – find the minimum/maximum value or calculate the sum of all items of a particular portion of the grid, update any of the grid index value etc. It seems, the problem is no different than typical segment tree problem unlike the dimension of data container. What can be a choice here is building a 2D Segment Tree. The idea of 2D segment tree is nothing but the **Quad Tree** – A tree data structure in which each external node has exactly four children. Quad trees are most often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions. The regions may be square or rectangular or may have arbitrary shapes. The data structure was named a quadtree by Raphael Frinkel and J. L. Bentley in 1974. ![Quad Tree][1] Fig: Quad Tree with recursive subdivision of 2D grid into 4 segments in every step (source: Wikipedia) Input: ------ There is no input. Output: ------- Output a line with a name of a tree based data structure as described in above problem description. ***Sample code in c++:*** #include<bits/stdc++.h> using namespace std; int main() { string name_of_data_structure = ""; // to be replaced with actual datastructure cout<<name_of_data_structure<<endl; } [1]: https://s3-ap-southeast-1.amazonaws.com/devskillimagestorage/questionimages/96dff96c-9a69-c8fa-6403-08d71148cd82_2cab013248ae4fd3845e72e917cbd90d_W399xH241.png


Problem Setter:

Kaidul Islam

Please login to submit solution to this problem.

Problem Limits

Language Time Limit (seconds)
C 1.00
C++ 1.00
C++14 1.00
C# 2.00
Go 2.00
Java 2.00
JavaScript 2.00
Objective-C 2.00
Perl 2.00
PHP 2.00
Python 2.00
Python3 2.00
Ruby 2.00
VB.Net 2.00

Problem Stats

152/288

Solve/Submission

Ranking

# User Language Timing
01 njrafi Cpp 0.00s
02 atrahman2012 Cpp 0.00s
03 alif_biswas Cpp 0.00s
04 SAIF_IIT8_JU Cpp 0.00s
05 mir003 Cpp 0.00s
06 badhansen123 Cpp 0.00s
07 Bisnu039 Cpp 0.00s
08 mh755628 Cpp14 0.00s
09 iammarajul Cpp 0.00s
10 tanvirshossain Cpp 0.00s
11 Fahim_41 Cpp14 0.00s
12 emrul Cpp 0.00s
13 Ahb_arif Cpp 0.00s
14 Robin008 Cpp 0.00s
15 rezaulhsagar Cpp 0.00s
16 Pure_Protea Cpp14 0.00s
17 duronto20 Cpp 0.00s
18 fayedanik Cpp 0.00s
19 Bruteforcekid Cpp 0.00s
20 prodipdatta7 Cpp14 0.00s
21 Ans_31 Cpp 0.00s
22 Islam_Rafat Cpp 0.00s
23 m3h3d1 Cpp 0.00s
24 anik_JU Cpp 0.00s
25 inam Cpp 0.00s
26 sitaula Cpp 0.00s
27 Anik_Modak Cpp 0.00s
28 aaman007 Cpp 0.00s
29 MdAbuBokor Cpp 0.00s
30 rashedul_riad Cpp 0.00s
31 hasanhp7 Cpp 0.00s
32 Riad_IIT7 Cpp 0.00s
33 durlov1234 Cpp 0.00s
34 Naim1611052 Cpp 0.00s
35 fr_sarker Cpp 0.00s
36 abufarhad Cpp 0.00s
37 Dragneel C 0.00s
38 mamunhossain Cpp 0.00s
39 Limon_88 Cpp14 0.00s
40 AlaminJust Cpp 0.00s
41 sabbir123 Cpp 0.00s
42 H_alexa Cpp 0.00s
43 SHOVON26 Cpp14 0.00s
44 tashfiq_ahm Cpp 0.00s
45 asfak Cpp 0.00s
46 somia Cpp14 0.00s
47 Towfiq379 Cpp 0.00s
48 obaydullahmhs Cpp 0.00s
49 Salam_35s Cpp 0.00s
50 Ayesha_Sultana Cpp 0.00s
Feedback

Your feedback is our precious!



Or call +88 02 9853138 for support