حساب مجموع نطاق بسرعة بإستخدام Prefix Sum
لما عندك استعلامات كتير على مجموع أجزاء من قائمة جهز المجاميع التراكمية مرة واحدة
المثال بإستخدام Python 3 لتوضيح الفكرة ويمكن تطبيق نفس المبدأ في لغات تانية
المثال العملي
values = [4, 2, 7, 1, 6]
prefix = [0]
for value in values:
prefix.append(prefix[-1] + value)
left, right = 1, 4
print(prefix[right] - prefix[left])النتيجة
10النطاق يبدأ عند الفهرس 1 وينتهي قبل 4 والمجموع هو 2 + 7 + 1 والتجهيز O(n) ثم كل استعلام O(1)
جرب بنفسك
احسب مجموع القائمة كلها ثم مجموع نطاق فاضي بنفس المعادلة