बाइनरी इंडेक्स ट्री (बीआईटी)

Question

के साथ कुछ लंबाई के बढ़ते उप-अनुक्रमों की कुल संख्या को कैसे प्राप्त करें बाइनरी इंडेक्स ट्री (बीआईटी) के साथ कुछ लंबाई के बढ़ते उप-अनुक्रमों की कुल संख्या मुझे कैसे मिल सकती है?

वास्तव में इस Spoj Online Judge

से एक समस्या है उदाहरण
मान लीजिए मैं एक सरणी 1,2,2,10

लंबाई 3 हैं 1,2,4 और 1,3,4

तो, इस सवाल का जवाब के उप दृश्यों में वृद्धि 2 है।

Answer 1

करते हैं:

dp[i, j] = number of increasing subsequences of length j that end at i 

एक आसान समाधान O(n^2 * k) में है:

for i = 1 to n do 
    dp[i, 1] = 1 

for i = 1 to n do 
    for j = 1 to i - 1 do 
    if array[i] > array[j] 
     for p = 2 to k do 
     dp[i, p] += dp[j, p - 1] 

जवाब dp[1, k] + dp[2, k] + ... + dp[n, k] है।

अब, यह काम करता है, लेकिन यह आपके दिए गए बाधाओं के लिए अक्षम है, क्योंकि n10000 तक जा सकता है। k काफी छोटा है, इसलिए हमें n से छुटकारा पाने के लिए एक रास्ता खोजने का प्रयास करना चाहिए।

चलिए एक और दृष्टिकोण आज़माएं। हमारे पास S भी है - हमारे सरणी में मानों पर ऊपरी सीमा। आइए इसके संबंध में एल्गोरिदम खोजने का प्रयास करें।

dp[i, j] = same as before 
num[i] = how many subsequences that end with i (element, not index this time) 
     have a certain length 

for i = 1 to n do 
    dp[i, 1] = 1 

for p = 2 to k do // for each length this time 
    num = {0} 

    for i = 2 to n do 
    // note: dp[1, p > 1] = 0 

    // how many that end with the previous element 
    // have length p - 1 
    num[ array[i - 1] ] += dp[i - 1, p - 1] 

    // append the current element to all those smaller than it 
    // that end an increasing subsequence of length p - 1, 
    // creating an increasing subsequence of length p 
    for j = 1 to array[i] - 1 do   
     dp[i, p] += num[j] 

इस जटिलता O(n * k * S) है, लेकिन हम काफी आसानी से O(n * k * log S) करने के लिए इसे कम कर सकते हैं। हमें केवल एक डेटा संरचना की आवश्यकता है जो हमें एक श्रेणी में तत्वों को कुशलतापूर्वक योग और अद्यतन करने देता है: segment trees, binary indexed trees आदि