بگذارید مقداری آرایه وجود داشته باشد. در غیاب تغییرات، ما می توانیم به سرعت (سریعتر از یک خط) مقدار برخی از توابع را در یک زیربخش از این آرایه پیدا کنیم. برای این کار باید از حافظه اضافی استفاده کنیم و یک پیش محاسبه انجام دهیم.
به عنوان مثال، ما باید به سرعت جمع را در قسمتی از آرایه پیدا کنیم.
بیایید آرایه ای از مجموع پیشوندها را بدست آوریم که در آن شاخص i مجموع همه عناصر آرایه با اندیس های کوچکتر یا مساوی i خواهد بود.
a[] – آرایه داده شده، p[] – آرایه ای از مجموع پیشوندها
تعداد آرایه p:
واضح است که p[0] = a[0]. توجه داشته باشید که به راحتی می توانیم p[i] را از طریق p[i – 1]، زیرا مقدار روی پیشوند i مقدار روی پیشوند i است – 1 + a[i].
بنابراین، کد محاسبه مجموع پیشوندها به صورت زیر است:
ایجاد شد
int a[n], p[n];
p[0] = a[0< /span>]؛
برای (int و = 1; i < n; i++)
p[i] = p[i - 1] + a[i];
علاوه بر این، ما توجه می کنیم که مجموع در بخش – تفاوت بین دو جمع روی پیشوند.
سبز = قرمز – آبی
بنابراین، اگر نیاز به یافتن مجموع بازه [l,r] باشد، پاسخ p[r] – p[l-1].
با این حال، اگر l – 1 عنصر ممکن است وجود نداشته باشد. برای انجام بدون اگر، می توانید 1-indexing را وارد کنید، و a[0] و p[0] مقادیر خنثی خواهند داشت (0 برای مجموع).
توجه داشته باشید که این تکنیک یک مورد خاص از فرمول گنجاندن-حذف است، بنابراین در این روش نه تنها مجموع، بلکه سایر توابع مانند ضرب و xor نیز امکان پذیر است.