ओ (लॉग एन) समय में किसी दिए गए रेंज में तत्वों की संख्या को खोजने के लिए कौन सी डेटा संरचना?

Question

मैं एक समस्या को हल कर रहा हूं और मुझे एहसास हुआ कि मुझे निम्नलिखित गुणों के साथ डेटा संरचना की आवश्यकता है लेकिन गुगलिंग के कुछ घंटों के बाद भी उसे नहीं मिल सकता है। मेरा मानना ​​है कि एसटीएल लाइब्रेरी बहुत अमीर है, इसलिए यह यहां नहीं पूछ रहा है।

1. किसी भी तत्व सम्मिलित O(log(n)) समय
2. में रूप में अच्छी तरह O(log(n)) समय में एक तत्व निकालें (repetetive लोगों को रोकने के लिए सक्षम होना चाहिए)।
3. i श्रेणी [क, ख], मैं कि गिनती O(log(n)) समय में मिलना चाहिए में elemenes की संख्या के लिए क्वेरी करने के लिए ..

मैं खरोंच से यह लिखने के लिए थे, तो भाग 1 के लिए चाहते हैं और 2, मैं एक set या multiset और मैं को संशोधित करेगा उनके find() विधि (जो O(log(N)) समय में चलता है) का उपयोग iterators के बजाय सूचकांक वापस जाने के लिए चाहते हैं, ताकि मैं (एन) समय abs(find(a)-find(b)) तो मैं लॉग में तत्वों की संख्या प्राप्त कर सकते हैं । लेकिन दुर्भाग्य से मेरे लिए, find() रिटर्न और इटेटरेटर।

मैंने multiset() में देखा है और मैं O(log(n)) समय में आवश्यकता 3 को पूरा नहीं कर सका। इसमें O(n) लगता है।

इसे आसानी से करने के लिए कोई संकेत?

Answer 1

हालांकि एसटीएल का हिस्सा नहीं है, आप Policy-Based Data Structures का उपयोग कर सकते हैं जो जीसीसी एक्सटेंशन का हिस्सा हैं; विशेष रूप से आप नीचे दिए गए order statistics tree को प्रारंभ कर सकते हैं। कोड किसी भी बाहरी पुस्तकालयों के बिना gcc साथ संकलित: इस कार्य के लिए

#include<iostream> 
#include<ext/pb_ds/assoc_container.hpp> 
#include<ext/pb_ds/tree_policy.hpp> 

using namespace __gnu_pbds; 
using namespace std; 

int main() 
{ 
    tree<int,   /* key    */ 
     null_type, /* mapped    */ 
     less<int>, /* compare function */ 
     rb_tree_tag, /* red-black tree tag */ 
     tree_order_statistics_node_update> tr; 

    for(int i = 0; i < 20; ++i) 
     tr.insert(i); 

    /* number of elements in the range [3, 10) */ 
    cout << tr.order_of_key(10) - tr.order_of_key(3); 
} 

Answer 2

हालांकि मानक पुस्तकालय वास्तव में अच्छी तरह से विशेष रुप से प्रदर्शित है, मुझे नहीं लगता कि आपको वहां इन विशेष आवश्यकताओं के साथ कुछ भी मिल जाएगा। जैसा कि आपने नोट किया है, सेट-जैसी संरचनाएं गैर-यादृच्छिक-पहुंच इटरेटर्स लौटती हैं - यादृच्छिक पहुंच प्रदान करने के लिए (या किसी प्रकार की दूरी फ़ंक्शन, जैसा कि आपको आवश्यकता है) महत्वपूर्ण जटिलता पेश करेगी।

को यहां बताए गए आप एक इंडेक्सेबल छोड़ सूची है, जो ओ (लॉग (एन)) प्रविष्टि, विलोपन, और अनुक्रमित देखने प्रदान करता है को लागू करने से अपने लक्ष्य को प्राप्त करने में सक्षम हो सकता है: कार्यान्वयन के लिए एक गाइड https://en.wikipedia.org/wiki/Skip_list#Indexable_skiplist

यहां पाया जा सकता है: http://cg.scs.carleton.ca/~morin/teaching/5408/refs/p90b.pdf

Answer 3

आपको इसे मानक या थोड़ा संशोधित बी-ट्री के साथ पूरा करने में सक्षम होना चाहिए।

आम तौर पर बी-ट्री कार्यान्वयन के लिए ओ (लॉग (एन)) अधिकांश मानक संचालन होते हैं।

Answer 4

दो स्पष्ट डेटा संरचनाओं हैं छोड़ सूची (जो जैक ओ रेली पहले ही उल्लेख किया गया है) और व्यवस्था आंकड़ा पेड़ किसी भिन्न रूप (जो Behzad उल्लेख है लेकिन वास्तव में समझा नहीं है)।

एक ऑर्डर सांख्यिकीय वृक्ष प्रत्येक नोड में जानकारी का एक अतिरिक्त टुकड़ा स्टोर करता है। आप कई अलग-अलग चीजों को स्टोर कर सकते हैं, लेकिन मुझे समझने में सबसे आसान लगता है कि यदि प्रत्येक नोड अपने बाएं उप-पेड़ में तत्वों की संख्या संग्रहीत करता है।

जब आप एक तत्व को स्टोर करने के लिए पेड़ पर चलते हैं, तो आप पेड़ में बाईं ओर उतरते समय गिनती बढ़ाते हैं।चूंकि आप केवल उन नोड्स को संशोधित कर रहे हैं जिन्हें आप किसी भी तरह से पार करेंगे, यह O(log N) सम्मिलन को परिवर्तित नहीं करता है। आप फिर से संतुलन है, तो आप उसके अनुसार समायोजित करने के लिए है (लेकिन, फिर से, आप केवल नोड्स में गिना जाता है आप पहले से ही संशोधित कर रहे हैं जब आप रोटेशन कर संशोधित कर रहे हैं, तो (फिर) आप समग्र जटिलता को प्रभावित नहीं करते।

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

Answer 5

यह निश्चित रूप से सबसे अधिक कुशल नहीं है, ओ (3 एन) दे रहा है, लेकिन यह संतुष्ट करता है उपरोक्त सूचीबद्ध, निकालें और दूरी मानदंड। निम्नलिखित एक लिंक्ड सूची, मानचित्र और unordered_map का उपयोग करता है।

सूची को बनाए रखने के लिए सूची का उपयोग किया जाता है। आम तौर पर क्रम में एक सूची में डालने से रैखिक समय होता है, लेकिन कुंजी के मानचित्र से list_iterator तक मदद के साथ, हम निरंतर समय में सम्मिलित कर सकते हैं। सूची में आदेशित डेटा संग्रहीत करने का लाभ यह है कि यह यादृच्छिक अभिगम इटरेटर्स का उपयोग करता है जिसका अर्थ है कि आप निरंतर समय प्राप्त कर सकते हैं std :: दूरी कॉल

मानचित्र का उपयोग नोड को सम्मिलित करने के लिए सूची में कहां के संकेत के लिए किया जाता है । यह दिए गए कुंजी के लिए एक नई नक्शा प्रविष्टि बनाकर किया जाता है, फिर इटरेटर को 1 तक घटाता है। इस नए इटरेटर का मूल्य हमें लिंक की गई सूची में उचित सम्मिलित स्थिति देता है।

unordered_map हमें एक ओ (logn) को हटाने और दूरी समय प्राप्त करने के लिए अनुमति देता है ओ (1) रैंडम एक्सेस सूची iterators के लिए देखने हमें देता है,।

class logn 
{ 
public: 
    using list_it = std::list<int>::iterator; 

    void insert(int i) 
    { 
     const bool first = list.empty(); 
     auto original_it = map.insert({i,list.end()}).first; // o(logn) 
     auto hint = original_it; 
     if (!first) 
      --hint; 
     umap[i] = list.insert(hint->second,i); // o(1) 
     original_it->second = umap[i]; 
    } 

    void remove(int i) 
    { 
     auto it = umap.find(i); // o(1) 
     list.erase(it->second); // o(1) 
     umap.erase(it);   // o(1) 
     map.erase(map.find(i)); // o(logn) 
    } 

    list_it get(int i) const 
    { 
     return umap.find(i)->second; 
    } 

    unsigned int distance(int lower, int upper) const 
    { 
     return std::distance(get(lower), get(upper)); 
    } 

private: 

    std::list<int> list; 
    std::unordered_map<int, list_it> umap; 
    std::map<int, list_it> map; 

};