बिल्ड डेटा संरचना रिवर्स प्रदर्शन और पाली logn समय

Question

n संख्या का एक अनुक्रम को देखते हुए में क्वेरी रिपोर्ट, {एक , एक , एक को, ..., एक_एन}। डेटा संरचना बनाएं जैसे कि निम्न ऑपरेशन पॉली-लॉगन समय में किया जा सकता है।

1. रिवर्स (मैं, जे):

   रिवर्स सभी रेंज में तत्वों मैंजे को, जिन्हें आप नीचे:
   मूल अनुक्रम: < ... एक_{i -1}, एक_मैं, एक_{मैं +1}, ..., एक_{जे -1}, एक_जे, एक_{j +1}, ...>
   स्वैप के बाद अनुक्रम: < ... एक_{मैं -1}, एक_जे, एक_{जे -1}, ..., एक_{मैं -1}, _i, एक_{जे +1} ...>

2. रिपोर्ट (मैं):

   रिपोर्ट मैं अनुक्रम में मई के तत्व, यानी एक_i।

यहाँ, पाली logn लॉग n के कुछ शक्ति का मतलब है। लॉग की तरह (n) · लॉग (n) स्वीकार्य हो सकता है।

[नोट: इस प्रश्न पूछने के लिए प्रो। बसवाना के लिए धन्यवाद।]

Answer 1

मैं एक द्विआधारी पेड़ का उपयोग करने का सोच रहा था, एक नोड एक वाम के साथ संवर्धित साथ | राइट सूचक और इस उप-वृक्ष में तत्वों की संख्या।

• सूचक Left पर सेट है फिर बाईं बच्चे पढ़ने से शुरू है, तो सही एक
• वरना (Right के लिए सेट) पढ़ा तो सही बच्चे पढ़ने से शुरू है, तो पढ़ एक
छोड़ दिया

Report काफी स्पष्ट है: O(log n)

Revert थोड़ा और अधिक जटिल है, और मैं अनिश्चित अगर यह वास्तव में काम करेंगे हूँ।

विचार एक विशेष उप-पेड़ (सबसे कम संभव) में उल्टा करने के लिए तत्वों के अनुक्रम को "पृथक" करना होगा। यह सबट्री रेंज [a..b] सहित [i..j]

• न्यूनतम सबट्री कि इस अनुक्रम (सूचक के परिवर्तन)
• [a..i-1] करने के लिए Revert आपरेशन लागू करें और [j+1..b]

यह सुनिश्चित नहीं हैं कि वास्तव में होता है उल्टा होता है हालांकि काम करता है:/

संपादित करें:

पिछला समाधान काम नहीं करता है :) मैं ऐसे समाधान की कल्पना नहीं कर सकता जो पेड़ को पुनर्व्यवस्थित नहीं करता है, और वे जटिलता आवश्यकताओं का सम्मान नहीं करते हैं।

अगर मैं किसी और को कुछ विचार देता हूं तो मैं इसे वहां छोड़ दूंगा, और जब तक मुझे कोई समाधान नहीं मिल जाता तब तक मैं इसे हटा दूंगा।

Answer 2

स्प्ले पेड़ + आपकी सजावट ओ (लॉग एन) amortized मिलता है। सामना करने वाली संरचनात्मक समस्याएं मैथ्यूयू को इस तथ्य से निपटाया जाता है कि ओ (लॉग एन) में अमूर्त समय में, हम रूट को किसी भी नोड में बदल सकते हैं जिसे हम पसंद करते हैं।

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