পাইথন - প্রিফিক্স সম (Prefix Sum) লিস্ট তৈরি করা

প্রিফিক্স সম (Prefix Sum) বা কিউমুলেটিভ সম (Cumulative Sum) লিস্ট হলো যেখানে প্রতিটি উপাদান ঐ পজিশন পর্যন্ত সব উপাদানের যোগফল। এটি রেঞ্জ কোয়েরি, সাবঅ্যারে সম, এবং অ্যালগরিদম অপ্টিমাইজেশনে খুব কাজে লাগে।

উদাহরণ

test_list = [3, 4, 1, 7, 9, 1]
# প্রিফিক্স সম: [3, 3+4, 3+4+1, 3+4+1+7, 3+4+1+7+9, 3+4+1+7+9+1]
#           = [3, 7, 8, 15, 24, 25]

পদ্ধতি: লিস্ট কাম্প্রিহেনশন + sum() + স্লাইসিং

test_list = [3, 4, 1, 7, 9, 1]
print("মূল লিস্ট:", test_list)

# প্রতিটি i এর জন্য ০ থেকে i পর্যন্ত সম
prefix_sum = [sum(test_list[:i+1]) for i in range(len(test_list))]

print("প্রিফিক্স সম লিস্ট:", prefix_sum)
# আউটপুট: [3, 7, 8, 15, 24, 25]

অপ্টিমাইজড ভার্সন: O(N) টাইম ( itertools.accumulate )

উপরের পদ্ধতি O(N²) কারণ প্রতিবার sum() O(N) নেয়। বড় লিস্টের জন্য itertools.accumulate ব্যবহার করুন যা O(N)।

from itertools import accumulate

test_list = [3, 4, 1, 7, 9, 1]
prefix_sum = list(accumulate(test_list))
print(prefix_sum)  # [3, 7, 8, 15, 24, 25]

NumPy ব্যবহার করে (সাংখ্যিক কাজের জন্য)

import numpy as np
arr = np.array([3, 4, 1, 7, 9, 1])
prefix_sum = np.cumsum(arr)
print(prefix_sum)  # [ 3  7  8 15 24 25]

ব্যবহারিক উদাহরণ: সাবঅ্যারে সম O(1)-এ বের করা

def range_sum(prefix, left, right):
    """prefix হলো প্রিফিক্স সম লিস্ট, ০-বেইজড ইনডেক্স"""
    if left == 0:
        return prefix[right]
    return prefix[right] - prefix[left - 1]

# ব্যবহার
prefix = [3, 7, 8, 15, 24, 25]
print(range_sum(prefix, 1, 3))  # ইনডেক্স ১ থেকে ৩: 4+1+7 = 12
print(range_sum(prefix, 0, 5))  # পুরো লিস্ট: 25

তুলনা