Scribd
Upload
427 views

2D Segment - Quad Tree Explanation With C++ - Stack Overflow

The document discusses 2D segment trees, also known as quadtrees, which are a data structure for storing and querying information in a 2D grid. It provides an intuitive explanation of how a 2D grid is recursively subdivided into quadrants to build the tree, with an example of a 4x4 grid. It also includes C++ code for implementing common operations on a 2D segment tree like initializing it from a 2D array, querying for maximum values in a region, and updating individual elements. Finally, it speculates on how this concept could potentially be extended to 3D segmentation by subdividing a 3D grid into octants instead of quadrants.

Uploaded by

Krutarth Patel
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
427 views

2D Segment - Quad Tree Explanation With C++ - Stack Overflow

The document discusses 2D segment trees, also known as quadtrees, which are a data structure for storing and querying information in a 2D grid. It provides an intuitive explanation of how a 2D grid is recursively subdivided into quadrants to build the tree, with an example of a 4x4 grid. It also includes C++ code for implementing common operations on a 2D segment tree like initializing it from a 2D array, querying for maximum values in a region, and updating individual elements. Finally, it speculates on how this concept could potentially be extended to 3D segmentation by subdividing a 3D grid into octants instead of quadrants.

Uploaded by

Krutarth Patel
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

signup

StackOverflowisaquestionandanswersiteforprofessionalandenthusiastprogrammers.It's100%free,no
registrationrequired.

login

tour

2D Segment/Quad Tree Explanation with C++ - Stack Overflow

8/8/2014

help

careers2.0

Takethe2minutetour

2DSegment/QuadTreeExplanationwithC++[onhold]
P.S.Thisismaybenotaduplicate.IsearchedSOandmakesurethatIdidn'tgetwhatIamseekingfor.
IamanACMproblemsolverandRecentlyI'velearntSegmentTreeforlineararrayandSegmentTree
withlazypropagation.ButIamencounteringsomeproblemswhichneed2Dsegmentstree(whichis
referredasQuadtreeinsomewhere).ButIcan'tfindanygoodtutorialsonit.IsearchedSOandfound
alinkhttp://emaxx.ru/algo/segment_treewhichisatutorialinRussianlanguage.
Ineedsomegoodexplanationwithsourcecode(preferablyinC++)on2DsegmentTree.Itistobe
notedthat,Iknowtypicalsegmenttreeprettywell.
c++ c algorithm tree

editedAug4at15:55
KaidulIslamSazal
1,439 6 26

askedAug4at15:11
pussyUtils
3 1

putonholdasunclearwhatyou'reaskingby,David
Eisenstat,vsoftco,EdChum,Yuushi2daysago
Pleaseclarifyyourspecificproblemoraddadditionaldetailstohighlightexactlywhatyouneed.Asit'scurrently
written,itshardtotellexactlywhatyou'reasking.SeetheHowtoAskpageforhelpclarifyingthisquestion.
Ifthisquestioncanberewordedtofittherulesinthehelpcenter,pleaseeditthequestion.

Canyoushowussomeexamplesofwhatyou'vetriedsofar?robbritAug4at15:13
Also,aquickGooglesearchfor"quadtree"givesmethis:gamedevelopment.tutsplus.com/tutorials/
robbritAug4at15:14
Quadtreesaredifferent.Lookup"rangetrees."A2Drangetreeisbasicallyjustatree(onx)ofsegmenttrees
(ony).tmyklebu2daysago
addacomment

1Answer
Well,asyousaidandIhopeyouknowsegmenttreewellenough.Iamgivingsomeintuitionbehind
multidimensionalsegmenttreefrommyblog.

SupposeyouregivenatwodimensionalN*N(foraprettylargeN,largeenoughtobenothandledby
bruteforce)gridofintegervalueandyoureaskedtoperformoperationsfindtheminimum/maximum
valueorcalculatethesumofallitemsofaparticularportionofthegrid,updateanyofthegridindex
valueetc.Itseems,theproblemisnodifferentthantypicalsegmenttreeproblemunlikethedimension
ofdatacontainer.Whatcanbeachoicehereisbuildinga2DSegmentTree.
Theideaof2DsegmenttreeisnothingbuttheQuadTreeAtreedatastructureinwhicheachexternal
nodehasexactlyfourchildren.Quadtreesaremostoftenusedtopartitionatwodimensionalspaceby
recursivelysubdividingitintofourquadrantsorregions.Theregionsmaybesquareorrectangularor
mayhavearbitraryshapes.ThedatastructurewasnamedaquadtreebyRaphaelFrinkelandJ.L.
Bentleyin1974.AsimilarpartitioningisalsoknownasQtree.
Therootofthetreecontainsthefullsegmentsthrough [(0,0),(N1,N1)].Andforeach
segment [(a1,b1),(a2,b2)],wesplittheminto [(a1,b1),((a1+a2)/2,(b1+
b2)/2))], [((a1+a2)/2+1,b1),(a2,(b1+b2)/2)], [(a1,(b1+
b2)/2+1),((a1+a2)/2,b2)]and [((a1+a2)/2+1,(b1+b2)/2+
1),(a2,b2)]until a1=b1and a2=b2.Thecostofbuildingasegmenttreeis
O(nlogn)andwithsegmenttreereadyansweringanRMQ(Rangemaximum/minimumquery)canbe
donein O(logn).
Suppose,youaregivenagridwithN=4.Thenthecorrespondingtreewillbe

http://stackoverflow.com/questions/25121878/2d-segment-quad-tree-explanation-with-c/

1/4

8/8/2014

2D Segment/Quad Tree Explanation with C++ - Stack Overflow

Asyousee,the4*4array [(0,0),(3,3)]issegmentedinto4subarrays [(0,0),(1,


1)], [(2,0),(3,1)], [(2,0),(1,3)]and [(2,2),(3,3)].Andfurther,
eachfourchunksaresegmentedintofoursmallerunitsForexamplesegment [(2,2),(3,3)]
willbe [(2,2),(2,2)], [(3,2),(3,2)], [(2,3),(2,3)]and [(3,3),
(3,3)].Thesesegmentsarethesmallestunitsonomorefurtherdivision.
Implementation
Thecodingpartisverysimilartosegmenttreeunlikethesegmentationpart.Thecodegivenhereis
programmingcontestfriendly(nopointer,memoryallocation/deallocationstuffandOOP
structure)andI'veusedthissnippetmanytimesincontests.
#include<bits/stdc++.h>
usingnamespacestd
#defineMax506
#defineINF(1<<30)
intP[Max][Max]//containerfor2Dgrid
/*2DSegmentTreenode*/
structPoint{
intx,y,mx
Point(){}
Point(intx,inty,intmx):x(x),y(y),mx(mx){}
booloperator<(constPoint&other)const{
returnmx<other.mx
}
}
structSegtree2d{
PointT[2*Max*Max]
intn,m
//initializeandconstructsegmenttree
voidinit(intn,intm){
this>n=n
this>m=m
build(1,1,1,n,m)
}
//builda2Dsegmenttreefromdata[(a1,b1),(a2,b2)]
//Time:O(nlogn)
Pointbuild(intnode,inta1,intb1,inta2,intb2){
//outofrange
if(a1>a2orb1>b2)
returndef()
3DSegmentation
//ifitisonlyasingleindex,assignvaluetonode
Iamafraidthat3DSegmentationhaseitherhardlyanyapplicationoritreallyexists.Iamjustgoingto
if(a1==a2andb1==b2)
givesomeintuitionofit.
returnT[node]=Point(a1,b1,P[a1][b1])
Itisnotimpossiblethatyouaregivena3Dgridandaskedtoperformsimilaroperationslike2Dsegment
//splitthetreeintofoursegments
tree.Inthiscase,Wecanconstructa3DSegmenttreejustlikewedidfor2Dgrid.
T[node]=def()
T[node]=maxNode(T[node],build(4*node2,a1,b1,(a1+a2)/2,(b1+b2)/2))
Wewillsplitthegridinto8smallersegmentsandrecursivelydosubdividinguntilthesmallestunit
T[node]=maxNode(T[node],build(4*node1,(a1+a2)/2+1,b1,a2,(b1+b2)/2))
appears.Thebelowpictureshowthissegmentationidea.
T[node]=maxNode(T[node],build(4*node+0,a1,(b1+b2)/2+1,(a1+a2)/2,b2))
T[node]=maxNode(T[node],build(4*node+1,(a1+a2)/2+1,(b1+b2)/2+1,a2,b2))
returnT[node]
}
//helperfunctionforquery(int,int,int,int)
Pointquery(intnode,inta1,intb1,inta2,intb2,intx1,inty1,intx2,inty2){
//ifweoutofrange,returndummy
if(x1>a2ory1>b2orx2<a1ory2<b1ora1>a2orb1>b2)
returndef()
//ifitiswithinrange,returnthenode
if(x1<=a1andy1<=b1anda2<=x2andb2<=y2)
returnT[node]

http://stackoverflow.com/questions/25121878/2d-segment-quad-tree-explanation-with-c/

2/4

8/8/2014

2D Segment/Quad Tree Explanation with C++ - Stack Overflow

For,1Dsegmenttree,Wedividethearrayinto2(2^1)segmentsandthatyieldsa log2(n)complexity
forparticularoperations.Againfor2Dsegmenttree,Wesplitthe2Dgridineverystepinto4(2^2)
segmentswhichensureeveryoperationswith log2(n)cost.Soinasimilarfashion,Weexpandthis
3Dtreebysubdividingthegridinto8(2^3)segments.
P.S.:The3DsegmenttreeismyownimaginationIdon'tknowifthereisanythinglikethat.Maybe
thereisabetterwayforboth2Dand3Dsegmenttreeoutthere,ButIthinkthesecodesufficefor
programmingcontestsasIhaveusedthesemanytimes.

Edit:
Theideaof3DsegmentationisnothingbuttheOctreeatreedatastructureinwhicheachinternal
nodehasexactlyeightchildren.Octreesaremostoftenusedtopartitionathreedimensionalspaceby
recursivelysubdividingitintoeightoctants.Octreesarethethreedimensionalanalogofquadtrees.

Octreesareoftenusedin3Dgraphicsand3Dgameengines.Ithasalotofotherapplicationslike
Spatialindexing,Nearestneighborsearch,Efficientcollisiondetectioninthreedimensionsandsomany.
Hopeithelps!
editedyesterday

answeredAug4at15:20
KaidulIslamSazal
1,439 6 26

http://stackoverflow.com/questions/25121878/2d-segment-quad-tree-explanation-with-c/

3/4

8/8/2014

2D Segment/Quad Tree Explanation with C++ - Stack Overflow

1 Thisisn'tright.3Dsegmentationhaslotsofhascommonuses.Octreesareusedtorepresentsolidsin
manygraphicsapplications.Givenacollectionofcirclesintheplaneandonedistinguishedcircle(P1,r1),
findthecircleinthecollection(P2,r2)minimizingdist(P1,P2)r1r2.GeneAug4at16:09

@GeneThanks.Ididn'tknowaboutOctree.Thanksforthisinformation,Iameditingmyanswer
KaidulIslamSazal2daysago

addacomment

Nottheansweryou'relookingfor?Browseotherquestionstagged c++ c algorithm


tree oraskyourownquestion.

http://stackoverflow.com/questions/25121878/2d-segment-quad-tree-explanation-with-c/

4/4

You might also like