खंडों के दो आयामी वृक्ष (तत्वों के समूह संशोधन के साथ)

समस्या का पूर्वानुमान और कथन

मुझे लगता है कि इस साइट के कई पाठकों ने इस तरह की उपयोगी संरचना को खंडों के पेड़ के रूप में सुना है। और यदि नहीं, तो आप इंटरनेट पर उसके बारे में बहुत सारी रोचक सामग्री पा सकते हैं ( यहां , हब्र पर लेख: एक और दो , Google, अंत में)।
यहां मैं खंडों के वृक्ष के द्वि-आयामी मामले के सामान्यीकरण का विश्लेषण करूंगा, और ( इस लेख के विपरीत) मैं तत्वों के समूह संशोधन के लिए समर्थन के साथ पेड़ के कार्यान्वयन पर विचार करूंगा।

सामान्य तौर पर, कई मामलों में, आप सामान्य रूप से सेगमेंट के पेड़ के बिना कर सकते हैं, उदाहरण के लिए, फेनविक पेड़ का उपयोग करें - यह सेगमेंट के पेड़ की तुलना में बहुत आसान लिखा गया है, एक छोटा स्थिर है, और जाहिर है बड़े आयामों पर लागू होता है। लेकिन इसके पास कम से कम दो मंत्री हैं: यह केवल प्रतिवर्ती संचालन को लागू करता है (इसे न्यूनतम / अधिकतम की गणना करने के लिए मजबूर करने के लिए, इसे बहुत विकृत होना होगा, और तब भी यह पूरी तरह से कार्रवाई की स्वतंत्रता नहीं देगा (अधिकतम में संशोधन - केवल मूल्य में वृद्धि करें, कम न करें, न्यूनतम - इसके विपरीत) )) और तत्वों के समूह संशोधन का समर्थन नहीं करता है।

ब्लॉक लंबाई के एक मुश्किल चयन के साथ एक अच्छा SQRT अपघटन भी कभी-कभी मदद करेगा, लेकिन फिर भी खंडों के पेड़ की शक्ति के साथ तुलना नहीं की जा सकती है।

तो चुनौती।

एक NxM फ़ील्ड है, दो प्रकार के अनुरोध किए जाने चाहिए:

1. निर्देशांक संतोषजनक के साथ कोशिकाओं के मूल्यों को बदलें। x पर </ x <= x2, y1 <= y <= y2 स्थितियों को संतोषजनक
2. X1 <= x <= x2, y1 <= y <= y2 को संतुष्ट करने वाले निर्देशांक के साथ कोशिकाओं से एक निश्चित फ़ंक्शन (साहचर्य बाइनरी ऑपरेशन) के मूल्य की गणना करें।

यहां मैं समस्या के समाधान के कार्यान्वयन का वर्णन करूंगा, जहां फ़ंक्शन का योग है। मुझे तुरंत यह कहना होगा कि मैं स्वयं इस निर्णय पर पहुँच गया (लगभग 15 घंटे के भीतर), इसलिए मैं एक सरल व्यक्ति के अस्तित्व को बाहर नहीं करता, और मुझे यह सुनने में भी खुशी होगी।

वृक्ष की संरचना

संरचना के आधार पर, खंडों के दो-आयामी वृक्ष खंडों के वृक्षों से खंडों के वृक्ष का प्रतिनिधित्व करते हैं (गहराई X_DEPTH के प्रत्येक नोड में गहराई Y_DEPTH का "नेस्टेड" वृक्ष है)। इसके बाद, पेड़ की गहराई तत्वों की संख्या का द्विआधारी लघुगणक है जिसे वह समायोजित कर सकता है। उदाहरण के लिए, आकृति 1 गहराई का एक पेड़ दिखाती है, जिसमें से प्रत्येक नोड में गहराई का एक पेड़ होता है। 2. ऐसा पेड़ फार्म के प्रश्नों को संसाधित कर सकता है [X1; x2] shows [0; 1], [y1; y2] shows [0; 3]।

हम इन पेड़ों के कोने (बाहरी और सभी नेस्टेड) ​​को साधारण एक आयामी पेड़ के रूप में संख्या देते हैं।
फिर संलग्न एक के प्रत्येक शीर्ष को समन्वित [x] [y] की विशेषता होगी, x बाहरी पेड़ के शीर्ष की संख्या है जिसमें यह स्थित है, और y आंतरिक है।

हम एक सेक्टर को कोशिकाओं द्वारा गठित एक आयत कहते हैं X1 <= x <= x2, y1 <= y <= y2। तब नेस्टेड सबट्री का प्रत्येक शीर्ष एक निश्चित क्षेत्र के लिए जिम्मेदार होता है।

"नेस्टेड" पेड़ के प्रत्येक नोड में, हम चार मापदंडों को संग्रहीत करेंगे:

• जोड़ें - वह मान जिसके द्वारा आप नेस्टेड सेक्टरों पर राशि का अनुरोध करते समय परिणाम बढ़ाना चाहते हैं (xth और yth निर्देशांक के वंशज)
• add_x - वह मान जिसके द्वारा परिणाम अपूर्ण रूप से नेस्टेड सेगमेंट पर राशि का अनुरोध करते समय बढ़ाया जाना चाहिए (yth समन्वय के साथ वंशज, लेकिन उसी xth के साथ)
• add_y - वह मान जिसके द्वारा परिणाम अपूर्ण रूप से नेस्टेड सेगमेंट पर राशि का अनुरोध करते समय बढ़ाया जाना चाहिए (xth समन्वय के साथ वंशज, लेकिन समान योग समन्वय के साथ)
• मान - शीर्ष के योग में योग (ऊपर सूचीबद्ध परिवर्धन की गिनती नहीं)

कंप्यूटर की मेमोरी में, यह समझना आसान है कि इस जानकारी को चार दो आयामी सरणियों द्वारा दर्शाया जाएगा।

संचालन प्रीप्रोसेसिंग

जब हम संशोधन ऑपरेशन करते हैं, तो एक आयामी मामले में, हम केवल दिए गए क्षेत्र के लिए परिभाषित शीर्ष सूची के मूल्यों को बदल देंगे। जब एक ही सेक्टर पर योग करते हैं, तो हम समान कार्यक्षेत्रों का उल्लेख करेंगे।

यदि हम शीर्ष [x0] [y0] के मूल्य को बदलते हैं, जो कि सेक्टर [x0_1; x0_2] [y0_1; y0_2] के लिए जिम्मेदार है, तो यह समझना मुश्किल नहीं है कि इस सेक्टर सहित सभी क्षेत्रों को जोड़े के रूप में पाया जा सकता है (x; y): X1 <= x0_1 और x0_2 <= x2 और y1 <= y0_1 और y0_2 <= y2। अर्थात्, यह xth, Y के लिए y के सेट X को इकट्ठा करने के लिए पर्याप्त है, और फिर XYY के सभी जोड़ों के माध्यम से सॉर्ट करता है।
ठीक है, इन समान सूचियों को इकट्ठा करने के लिए, आपको सबसे ऊपर से गुजरना होगा, जैसे कि एक आयामी पेड़ पर एक प्रश्न के मामले में।

एक विशिष्ट जोड़ी (x; y) को ध्यान में रखते हुए, आप आसानी से xl, xr, yl, yr - वर्तमान वर्टेक्स के secotra की सीमा, साथ ही xc और yc - xth और yth axes के साथ चौराहों पर तत्वों की संख्या की गणना कर सकते हैं।

संशोधन संचालन

1. यदि अनुरोध में पूरी तरह से वर्तमान वर्टेक्स का क्षेत्र शामिल है, तो आपको वैल वर्टिक्स वर्टिस जोड़ने की जरूरत है (वैल को एक्सथ और यथ द्वारा सभी वंशों में जोड़ा जाना चाहिए):
   जोड़ + = घाटी;
   
2. यदि अनुरोध में वर्तमान क्षेत्र केवल xth समन्वय में शामिल है, तो add_y बदलें:
   add_y + = val * xc;
   
3. यदि अनुरोध में वर्तमान क्षेत्र केवल yth समन्वय में है, तो add_x बदलें:
   add_x + = val * yc;
   
4. यदि अनुरोध में एक क्षेत्र शामिल नहीं है:
   मान + = वैल * xc * yc;
   

ऐड के साथ, मुझे लगता है कि सब कुछ स्पष्ट है (एक आयामी मामला देखें)।

जब एक अनुरोध में y-th समन्वय में वर्तमान क्षेत्र शामिल होता है, तो y-th में ऐसे वंशज हो सकते हैं जो इस अनुरोध में प्रभावित नहीं होंगे, लेकिन राशि के अनुरोध पर भविष्य में होंगे। इसलिए हम add_x को बढ़ाते हैं।
इसी तरह add_y के साथ।

और अंत में, यदि पिछली तीन स्थितियों में से कोई भी पूरा नहीं हुआ है, तो इस शीर्ष के प्रत्यक्ष वंशज के बीच, एक बदल जाएगा, और दूसरा नहीं होगा। इसलिए, इस परिवर्तन को ध्यान में रखा जाना चाहिए, लेकिन आगे वितरित नहीं किया जाना चाहिए। मान बढ़ाएँ।

संक्षेपण ऑपरेशन

क्वेरी परिणाम को रीसेट करें, जिसे हम गणना करेंगे। प्रीप्रोसेसिंग के अलावा, हम उस अनुरोध के उस हिस्से की सीमाओं की गणना करते हैं जिसे हम किसी दिए गए शीर्ष (इच्छित भाग की सीमाओं) के लिए देख रहे हैं:

xvl = max (xl, X1), xvr = min (xr, x2), yvl = max (yl, y1), yvr = min (yr, y2)

1. हमें वर्तमान क्षेत्र में पड़ी सभी अनुरोध कोशिकाओं को जोड़ने के लिए वर्तमान शीर्ष जोड़ने की आवश्यकता है:
   Res + = * * xc * yc जोड़ें;
   
2. यदि वांछित भाग xth रेंज में वर्टेक्स सेक्टर के बराबर है:
   Res + = add_x * yc;
   
3. यदि वांछित भाग y- वें श्रेणी में शीर्ष क्षेत्र के बराबर है:
   res + = add_y * xc;
   
4. यदि वर्तमान शीर्ष का क्षेत्र अनुरोध में पूरी तरह से निहित है (हम नीचे नहीं जाएंगे):
   Res + = मूल्य;
   

Asymptotics

जैसा कि आप विवरण से देख सकते हैं, यह समाधान O (N * X_DEPTH * Y_DEPTH) के लिए काम करेगा, जहाँ N अनुरोधों की संख्या है।

कार्यान्वयन

आप इस समाधान के कार्यान्वयन को http://dl.dropbox.com/u/3693476/articles/segtree2d/segtree2d.cpp (फ़ाइल समस्या का समाधान, D से फ़ाइल http://dl.dropbox.com/u/ पर देख सकते हैं) 3693476 / लेख / segtree2d / problems01.pdf )। यदि आप अपने समाधान को डीबग करने के लिए इस कार्य के लिए परीक्षण प्राप्त करना चाहते हैं, तो अपना अनुरोध मेरे मेलबॉक्स george.agapov@gmail.com पर लिखें।

PS आप सभी का ध्यान देने के लिए धन्यवाद, मुझे उम्मीद है कि यह लेख किसी के लिए उपयोगी होगा।