جمع پیشوندی

پیاده‌سازی

نحوه پیاده‌سازی جمع پیشوندی در زبان‌های جاوا، پایتون و سی {به انگلیسی:به ترتیب:C, python, java} نشان داده شده‌است.

پیاده‌سازی با کد C

int* prefixSums(int[] input, int[] output, int length) {
    output[0] = input[0];
    int i;
    for (i = 1; i <length; i++)
        output[i] = output[i - 1] + input[i];

    return output;

پیاده‌سازی با کد جاوا

static int[] prefixSums(int[] input, int[] output) {
    output[0] = input[0];
    for(int i = 0; i <input.length; i++)
        output[i] = output[i - 1] + input[i];
    return output;}

پیاده‌سازی پایتون

def prefixSums(input, output):
    output[0] = input[0];
    for i in range(1, len(input)):
        output[i] = output[i - 1] + input[i]

کاربردها

مرتب‌سازی شمارشی گونه‌ای از مرتب‌سازی‌های خطی است که بدون مقایسه، عمل مرتب‌سازی عناصر یک آرایه را انجام می‌دهد. در مرتب‌سازی شمارشی، از جمع پیشوندی برای یافتن جایگاه هر عنصر در آرایه مرتب‌شده، استفاده می‌شود.
در رتبه‌بندی لیست‌ها، برای تبدیل یک لیست پیوندی به یک آرایه خروجی، از جمع پیشوندی استفاده می‌شود بدین نحو که یک آرایهٔ ورودی از ۱ها به اندازه طول لیست پیوندی ساخته می‌شود سپس با استفاده از جمع پیشوندی این آرایه، اندیس متناظر برای نگاشتن هر عنصر در لیست پیوندی به آرایه خروجی موردنظر ایجاد می‌شود که نشان‌دهنده موقعیت آن عنصر در آرایه خروجی است.
یکی از داده ساختارهای پرکاربرد برای ذخیره‌سازی مجموعه‌ای از اطلاعات که به‌طور پیوسته به‌روزرسانی می‌شود یا به آن اطلاعات جدیدی اضافه می‌شود، درخت فنویک است. درخت فنویک مجموع چند عدد اول یک آرایه، به همراه به‌روزرسانی کردن عناصر آن آرایه را در مرتبه زمانی (O(logn انجام می‌دهد. این درخت برای محاسبهٔ مجموع چند عدد اول یک آرایه به همراه به‌روزرسانی، از جمع پیشوندی استفاده می‌کند.
برای پیاده‌سازی برخی از توابع در یک درخت، مانند ارتفاع و عمق یک گره، از جمع پیشوندی استفاده می‌شود. به عنوان مثال برای محاسبهٔ ارتفاع یک گره، می‌توان با داشتن ارتفاع فرزندهای چپ و راست آن گره و در نظر گرفتن بزرگ‌ترین آنها، ارتفاع آن گره را بدست‌آورد. برای محاسبهٔ عمق یک گره، با داشتن عمق پدر آن گره و جمع آن با یک، می‌توان عمق آن گره را بدست‌آورد.
همچنین در پیشوندهای موازی (استفاده از ضرب به عنوان عملیات متداول پایه) می‌تواند برای ساخت الگوریتم‌های سریع برای درون‌یابی چندجمله‌ای موازی استفاده شود. به‌طور خاص، می‌توان از آن برای محاسبهٔ ضرایب تقسیم فرم نیوتن در چندجمله‌ای‌های درون‌یابی استفاده کرد.

جمع پیشوندی موازی

مزیتی که جمع پیشوندی موازی نسبت به غیر موازی دارد، حافظه به کارگرفته‌شده می‌باشد. حافظهٔ جمع پیشوندی موازی از مرتبه (O(logn می‌باشد در حالی‌که حافظهٔ به کارگرفته‌شده در حالت غیرموازی از مرتبهٔ (O(n می‌باشد. ساخت جمع پیشوندی موازی ۲ مرحله دارد:
مرحله ۱:ساخت یک درخت دودویی
در این مرحله، درخت دودویی ساخته می‌شود که هر گرهٔ آن، جمع پیشوندی یک بازه مشخص را در خود نگه می‌دارد. ریشهٔ درخت، جمع پیشوندی بازهٔ کل اعداد ورودی را نگه می‌دارد. اگر گره‌ای، جمع پیشوندی بازهٔ  را در خود نگه دارد، فرزند چپ آن بازهٔ   و فرزند راست آن بازهٔ   را نگه می‌دارد. همچنین هر برگ این درخت، بازهٔ را نگه می‌دارد که برابر است با ورودی عنصر ام.  همان‌طور که ملاحظه می‌شود برای ساخت این درخت دودویی از الگوریتم تقسیم و حل استفاده می‌شود.
مرحله ۲: پاس دادن مقدار «از چپ» {انگلیسی: from left} و ساخت آرایهٔ خروجی

هر گره یک دادهٔ اضافی به نام «از چپ» را نگه می‌دارد. به ریشهٔ درخت مقدار «از چپ» صفر داده می‌شود. فرزند چپ هر گره، مقدار «از چپ» را از پدر خود می‌گیرد، فرزند راست هر گره، مجموعی از مقادیر «از چپ» پدر و جمع پیشوندی بازهٔ ذخیره‌شده در فرزند چپ گره پدر را نگه می‌دارد. در نهایت، خروجی ام آرایهٔ جمع پیشوندی از جمع مقادیر «از چپ» برگ ام با جمع پیشوندی بازهٔ ذخیره‌شده در آن برگ (بازهٔ ) حاصل می‌شود.