Skip to content

012 — BIT-accelerated LIS

Source

  • Original source: self-exercise bridging to DP (folder 12 LIS-এর সাথে সেতু)
  • Platform: self-exercise — judge নেই, ইচ্ছে করেই DP + BIT-এর সংযোগ অনুশীলন
  • Topic: segment tree and fenwick tree
  • Difficulty: Medium
  • Pattern: BIT accelerates DP transitions (value-indexed tree)
  • Basic idea inherited from: folder 12 LIS + এই folder (BIT over values)

1. Problem in simple words

একটা array a দেওয়া। Longest Increasing Subsequence (LIS)-এর দৈর্ঘ্য বের করো — strictly increasing এমন সবচেয়ে লম্বা subsequence-এর length। (Folder 12 শেষ করার পরে এই note লেখো।) লক্ষ্য: O(n^2) DP-টাকে একটা value-indexed BIT দিয়ে O(n log n)-এ তোলা।

a = [3, 1, 4, 1, 5, 9, 2, 6]

একটা LIS: [1, 4, 5, 9]  বা  [1, 4, 5, 6]   ->  length 4

2. Which basic idea does this inherit from?

এটা folder 12-র LIS DP আর এই folder-এর BIT-over-values-এর সংযোগস্থল। LIS-এর classic DP তুমি folder 12-তে দেখেছ; এখানে সেই DP-র "আমার আগে আমার চেয়ে ছোট সব value-র মধ্যে best কে?" — এই transition-টা BIT দিয়ে দ্রুত করি।

3. What is the hidden math or logic?

লুকানো logic: LIS DP বলে dp[i] = 1 + max(dp[j] for j < i, a[j] < a[i])। ভেতরের max-টা একটা prefix-max over values — "আমার চেয়ে ছোট সব value-র মধ্যে এ পর্যন্ত দেখা সর্বোচ্চ dp কত?"। BIT এই prefix-max O(log n)-এ দিতে পারে।

4. Which data structure is needed?

একটা max-Fenwick tree, value-দের rank-এ indexed। সাধারণ BIT sum জমায়; এখানে আমরা একই lowbit-navigation-এ max জমাই। Value বড় হতে পারে, তাই আগে coordinate compression।

5. Why this data structure fits

LIS-এর bottleneck হলো প্রতি element-এ "আগের ছোট value-গুলোর best dp"। সেটা একটা value-axis-এর উপর prefix-max query — আর max-BIT ঠিক এই prefix-max (1..r) O(log n)-এ দেয়, point update-ও O(log n)। তাই n element-এ O(n log n)। (Max prefix invertible না বলে এটা শুধু prefix [1..r] max-এ কাজ করে — arbitrary range-min/max-এ segment tree লাগত, কিন্তু LIS-এ prefix-ই যথেষ্ট।)

6. Real-life analogy

ভাবো তুমি পাহাড়ে চড়ছ, প্রতিটা ক্যাম্পের একটা উচ্চতা আছে। প্রতিটা নতুন ক্যাম্পে দাঁড়িয়ে জানতে চাও — আমার চেয়ে নিচু সব ক্যাম্পের মধ্যে কোনটা থেকে এলে এ পর্যন্ত সবচেয়ে লম্বা চড়াই-পথ হবে? প্রতিবার সব নিচু ক্যাম্প ঘুরে দেখার বদলে, উচ্চতা-অনুযায়ী সাজানো একটা "best so far" board রাখো; নতুন উচ্চতায় শুধু তোমার-নিচের অংশটা দেখো।

7. Visual explanation

a = [3, 1, 4, 1, 5]   compressed rank (1->1, 3->2, 4->3, 5->4):
                       a:     3  1  4  1  5
                       rank:  2  1  3  1  4

প্রক্রিয়া বাঁ -> ডান, max-BIT-এ rank-এর জায়গায় dp জমাই:
  x=3 (rank2): prefix_max(1) = 0  -> dp=1;  update(2, 1)
  x=1 (rank1): prefix_max(0) = 0  -> dp=1;  update(1, 1)
  x=4 (rank3): prefix_max(2) = 1  -> dp=2;  update(3, 2)
  x=1 (rank1): prefix_max(0) = 0  -> dp=1;  update(1, 1)  (already 1)
  x=5 (rank4): prefix_max(3) = 2  -> dp=3;  update(4, 3)
                                     answer = max dp = 3   ([1,4,5])

8. Example input and output

input:  a = [3, 1, 4, 1, 5, 9, 2, 6]
output: 4            ([1,4,5,9] বা [1,4,5,6])

input:  a = [7, 7, 7]
output: 1            (strictly increasing, তাই duplicate গোনা যায় না)

input:  a = [1, 2, 3, 4, 5]
output: 5            (পুরোটাই increasing)

9. Brute force thinking

Classic O(n^2) DP: প্রতি i-র জন্য সব j < i ঘুরে, a[j] < a[i] হলে dp[i] = max(dp[i], dp[j] + 1)।

for i in range(n):
    dp[i] = 1
    for j in range(i):
        if a[j] < a[i]:
            dp[i] = max(dp[i], dp[j] + 1)
answer = max(dp)

নির্ভুল, আর এটাই আমাদের reference।

10. Why brute force is slow

দুই nested loop = O(n^2)। n = 100,000 হলে 10^10 — TLE। ভেতরের loop আসলে একটা prefix-max query; সেটা BIT-এ O(log n)-এ করলে পুরোটা O(n log n)।

11. Key observation

মূল observation: DP-র ভেতরের max(dp[j] for a[j] < a[i]) একটা prefix-max over values। i বাড়ার সাথে সাথে আমরা value-axis-এ dp জমাচ্ছি; নতুন element-এ শুধু "আমার rank-এর নিচের সব" prefix-max চাই। এটাই BIT-এর কাজ।

12. Optimized intuition

element-গুলো বাঁ থেকে ডানে process করো (index-order রাখা জরুরি, যাতে শুধু আগের element-রাই BIT-এ থাকে)। প্রতি x-এ: rank r বের করো, best = prefix_max(r - 1) (strictly ছোট value), dp = best + 1, তারপর point_update_max(r, dp)। উত্তর = সব dp-র max। Strict চাই বলে r - 1 (নিজের সমান value বাদ)।

13. Thinking tweak

মোচড়: DP transition-কে একটা "range query"-তে দেখো। তখন ধীর ভেতরের loop-টাকে একটা data structure (এখানে value-indexed max-BIT) দিয়ে replace করা যায়। এই DP + BIT/segment tree জোড়া অনেক counting/optimization DP-কে দ্রুত করে।

14. Step-by-step dry run

a = [3, 1, 4, 1, 5], compressed rank {1:1, 3:2, 4:3, 5:4}, max-BIT খালি। বাঁ → ডান:

  1. x=3 (r=2): prefix_max(1)=0 → dp=1; update(2, 1)।
  2. x=1 (r=1): prefix_max(0)=0 → dp=1; update(1, 1)।
  3. x=4 (r=3): prefix_max(2)=1 → dp=2; update(3, 2)।
  4. x=1 (r=1): prefix_max(0)=0 → dp=1; update(1, 1) (1-ই থাকে)।
  5. x=5 (r=4): prefix_max(3)=2 → dp=3; update(4, 3)।
  6. answer = max(1,1,2,1,3) = 3। ✓

15. Python solution

class FenwickMax:
    """1-indexed max-Fenwick। index মানে একটা VALUE-র rank।
    update(i, val): tree[i]-কে max(., val) করো (point);
    prefix_max(i): 1..i-র max। দুটোই O(log n)।
    সতর্কতা: max invertible নয় -> শুধু PREFIX [1..i] max পাওয়া যায়,
    arbitrary range নয় (এই problem-এ prefix-ই যথেষ্ট)।"""

    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)         # dp মান >= 1, তাই 0 = "এখনো কিছু নেই"

    def update(self, i, val):
        while i <= self.n:
            if val > self.tree[i]:
                self.tree[i] = val
            i += i & (-i)

    def prefix_max(self, i):
        best = 0
        while i > 0:
            if self.tree[i] > best:
                best = self.tree[i]
            i -= i & (-i)
        return best


def lis_length_bit(a):
    if not a:
        return 0
    # coordinate compression: value -> 1-indexed rank
    order = sorted(set(a))
    rank = {v: idx + 1 for idx, v in enumerate(order)}
    bit = FenwickMax(len(order))
    best_overall = 0
    for x in a:                            # বাঁ -> ডান, index-order
        r = rank[x]
        cur = bit.prefix_max(r - 1) + 1    # strictly ছোট value-র best + 1
        bit.update(r, cur)
        if cur > best_overall:
            best_overall = cur
    return best_overall


def lis_length_brute(a):
    # obviously-correct O(n^2) DP reference
    n = len(a)
    if n == 0:
        return 0
    dp = [1] * n
    for i in range(n):
        for j in range(i):
            if a[j] < a[i] and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
    return max(dp)


# ---- tests ----
a = [3, 1, 4, 1, 5, 9, 2, 6]
assert lis_length_bit(a) == 4
assert lis_length_brute(a) == 4

assert lis_length_bit([7, 7, 7]) == 1            # strict: duplicate গোনা যায় না
assert lis_length_bit([1, 2, 3, 4, 5]) == 5      # পুরোটাই increasing
assert lis_length_bit([5, 4, 3, 2, 1]) == 1      # পুরোটাই decreasing
assert lis_length_bit([]) == 0                   # empty
assert lis_length_bit([42]) == 1                 # single

# BIT version সবসময় brute DP-র সাথে একমত (duplicate, negative-সহ)
import random
for _ in range(400):
    arr = [random.randint(-5, 5) for _ in range(random.randint(0, 14))]
    assert lis_length_bit(arr) == lis_length_brute(arr)

print("সব test pass!")

16. Line-by-line code explanation

  • FenwickMax — সাধারণ BIT-এর lowbit navigation, কিন্তু sum-এর বদলে point-max জমায় (prefix_max শুধু [1..i]-এ valid)।
  • order/rank — coordinate compression, value → 1..k rank; বড়/negative value সামলায়।
  • lis_length_bit — বাঁ থেকে ডানে; prefix_max(r-1) দেয় strictly ছোট value-র best dp, তারপর update(r, cur)।
  • r - 1 — strict increasing চাই বলে নিজের সমান value বাদ।
  • brute — O(n^2) DP, নির্ভুল reference।

17. Output walkthrough

[3,1,4,1,5,9,2,6]-এ BIT version দেয় 4, brute DP-ও 4। তারপর 400-টা random array-তে — duplicate আর negative-সহ — দুই পদ্ধতি সবসময় একমত। [7,7,7] strict বলে 1 দেয়। শেষে print: সব test pass!।

18. Time complexity

O(n log n): প্রতি element-এ একটা prefix_max + একটা update, প্রতিটা O(log n); compression-এর sort-ও O(n log n)।

19. Space complexity

O(n): max-BIT array + rank map।

20. Common mistakes

  • prefix_max(r) লেখা যেখানে prefix_max(r - 1) দরকার — তাহলে নিজের সমান value-ও ধরা পড়ে, strict ভেঙে যায়।
  • max-BIT-এ arbitrary range-max চাওয়া — max invertible নয়, শুধু prefix [1..i] valid; arbitrary range-এ segment tree লাগত।
  • Coordinate compression বাদ দেওয়া — বড়/negative value-তে BIT index ভেঙে পড়ে।
  • element-গুলো index-order ছাড়া process করা — তখন ভবিষ্যতের element BIT-এ ঢুকে subsequence-এর order ভাঙে।

21. Which basic problem this inherits from

ভিত্তি: folder 12-র LIS DP + এই folder-এর BIT-over-values (../fenwick-tree.md section 9)। এটা দেখায় কীভাবে একটা DP transition-কে range query-তে দেখে data structure দিয়ে accelerate করা যায়।

22. Similar harder problems

23. Pattern learned

BIT accelerates DP transitions: যখন একটা DP-র ভেতরের loop আসলে "value-axis-এর উপর prefix max/sum", তখন value-indexed BIT সেটা O(log n)-এ করে পুরো DP-কে O(n log n)-এ তোলে। DP + data-structure সংযোগের প্রথম স্বাদ।

24. Final summary

ভবিষ্যতের আমাকে: LIS-এর ভেতরের max(dp[j] : a[j] < a[i]) একটা prefix-max over compressed values — value-indexed max-BIT দিয়ে O(log n)। মূল শিক্ষা: একটা DP transition-কে range query হিসেবে চিনতে পারলে BIT/segment tree দিয়ে সেটা accelerate করা যায়।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।