कार्टिसियन पेड़ निहित कुंजी + अंतरिक्ष संपीड़न द्वारा

इस लेख को पढ़ने से पहले, आपको यह समझना होगा कि कार्टिसियन ट्री निहित कुंजी से क्या है (यह एक से अधिक लेख का विषय है, इसलिए यहां इसके बारे में पढ़ना बेहतर है )। स्पेस कम्प्रेशन एक ऐसी विधि है जिसका उपयोग डेटा के एक टुकड़े पर सेक करने के लिए किया जाता है। उदाहरण के लिए, सेट {1, 1, 1, 2, 2, 2, 3, 1, 1} को स्टोर करने के बजाय, हम {1 x 3, 2 x 3, 3 x 1, 1 x 2} को स्टोर करेंगे।
अब इस विधि का उपयोग करके अंतरिक्ष को संपीड़ित करने का प्रयास करें और किसी भी सेगमेंट के साथ ऑनलाइन संचालन करने में सक्षम हों।

मैं ऐसे पेड़ों को तुरंत लागू करने का अधिकार देता हूँ

struct treap_node { int x, y; treap_node *l, *r, *p; int width; int val; //    void push() { //       } //  ,     void update() { x = width; if (l) x += l -> x; if (r) x += r -> x; if (l) l -> p = this; if (r) r -> p = this; //   ,    ,      } treap_node(int _width, int _val) { //   // val -  , width -    y = (rand() << 16) + rand(); l = r = p = NULL; width = _width; val = _val; update(); } }; //  2  treap_node* merge(treap_node *l, treap_node *r) { if (l == NULL) return r; if (r == NULL) return l; if (l -> y >= r -> y) { l -> push(); l -> r = merge(l -> r, r); l -> update(); return l; } else { r -> push(); r -> l = merge(l, r -> l); r -> update(); return r; } } //  1   2 void split(treap_node *t, int x, treap_node *&l, treap_node *&r) { if (t == NULL) { l = r = NULL; return; } t -> push(); if ((t -> l == NULL ? 0 : t -> l -> x) >= x) { split(t -> l, x, l, t -> l); if (l != NULL) l -> p = NULL; t -> update(); r = t; return; } else if ((t -> l == NULL ? 0 : t -> l -> x) + t -> width <= x) { split(t -> r, x - (t -> l == NULL ? 0 : t -> l -> x) - t -> width, t -> r, r); if (r != NULL) r -> p = NULL; t -> update(); l = t; return; } else { //   .       ,      treap_node *t1 = new treap_node(x - (t -> l == NULL ? 0 : t -> l -> x), t -> val); treap_node *t2 = new treap_node(t -> width - t1 -> width, t -> val); l = merge(t -> l, t1); r = merge(t2, t -> r); l -> p = NULL; r -> p = NULL; delete(t); } } 

ध्यान दें कि सामान्य कार्टेशियन पेड़ों की तुलना में, हमारी संरचना में चौड़ाई की संपत्ति दिखाई दी - हमारे वर्तमान शीर्ष पर संग्रहीत खंड की चौड़ाई। और वैल का मतलब ही होता है।
एक और बड़ा बदलाव - स्प्लिट फंक्शन

 else { //   .       ,      treap_node *t1 = new treap_node(x - (t -> l == NULL ? 0 : t -> l -> x), t -> val); treap_node *t2 = new treap_node(t -> width - t1 -> width, t -> val); l = merge(t -> l, t1); r = merge(t2, t -> r); l -> p = NULL; r -> p = NULL; delete(t); } 

यहाँ अगर का एक और हिस्सा है। जो खंड के 2 उप-खंडों में विभाजन को संदर्भित करता है। और फिर बाईं और दाईं ओर gluing।

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