آبشاره‌سازی جزءبه‌جزء
مثال

به عنوان یک مثال ساده از آبشاره‌سازی جزءبه‌جزء، این مسئله را در نظر بگیرید: تعداد k لیست مرتب شده از اعداد حقیقی به ما داده شده‌است. مجموع تعداد اعضای این لیست‌ها روی هم n است. یعنی اگر هر لیست را با Li نشان دهیم، Σ|Li|=n. می‌خواهیم این لیست‌ها را طوری پردازش کنیم که بتوانیم جستجوهای دودویی را به دنبال مقدار خواسته شدهٔ q در هر یک از این k لیست انجام دهیم. برای مثال، به ازای n = ۴ و k = ۱۷:
L1 = ۲٫۴، ۶٫۴، ۶٫۵، ۸٫۰، ۹٫۳
L2 = ۲٫۳، ۲٫۵، ۲٫۶
L3 = ۱٫۳، ۴٫۴، ۶٫۲، ۶٫۶
L4 = ۱٫۱، ۳٫۵، ۴٫۶، ۷٫۹، ۸٫۱
ساده‌ترین راه حل برای این مسئلهٔ جستجو، ذخیره کردن هر لیست به طور جداگانه (در یک آرایه) است. در این صورت به حافظهٔ اضافی از مرتبهٔ n نیاز داریم. جستجو را در هر یک از این k لیست به طور جداگانه انجام می‌دهیم. بدترین حالت زمانی رخ می‌دهد که تعداد اعضای لیست‌ها برابر و به میزان n/k باشد. در این صورت زمان یک جستجو، در هر لیست از مرتبهٔ (log(n/k و در نتیجه زمان کلی یک جستجو از مرتبهٔ (klog(n/k خواهد بود.
راه حل دوم جستجوهای سریع تری را ممکن می‌کند اما فضای بیشتری از حافظه می‌گیرد. ما می‌توانیم k لیست را در یک لیست بزرگ L با هم ادغام کنیم و به ازای هر مورد x از لیست L، نتایج جستجوهای x در لیست‌های کوچکتر Li را قرار دهیم. یک المان از لیست ادغام شده را با x[a, b, c, d] نشان می‌دهیم، که x یک مقدار، و a, b, c, d مکان‌های مقادیر عنصر بعدی x، در هر یک از لیست‌های ورودی است (فرض بر این است که نخستین مکان را با ۰ نشان می‌دهیم). با توجه به مرتب بودن لیست‌های ورودی، منظور از عنصر بعدی، عنصر بلافاصله بزرگ‌تر یا حد اقل مساوی با x است. (اگر چنین عنصری وجود نداشت، مکان بعد از آخرین خانهٔ لیست را، قرار داد می‌کنیم) در این صورت خواهیم داشت:
L = ۱٫۱[۰٬۰٬۰٬۰], ۱٫۳[۰٬۰٬۰٬۱], ۲٫۳[۰٬۰٬۱٬۱], ۲٫۴[۰٬۱٬۱٬۱], ۲٫۵[۱٬۱٬۱٬۱], ۲٫۶[۱٬۲٬۱٬۱],
۳٫۵[۱٬۳٬۱٬۱], ۴٫۴[۱٬۳٬۱٬۲], ۴٫۶[۱٬۳٬۲٬۲], ۶٫۲[۱٬۳٬۲٬۳], ۶٫۴[۱٬۳٬۳٬۳], ۶٫۵[۲٬۳٬۳٬۳],
۶٫۶[۳٬۳٬۳٬۳], ۷٫۹[۳٬۳٬۴٬۳], ۸٫۰[۳٬۳٬۴٬۴], ۸٫۱[۴٬۳٬۴٬۴], ۹٫۳[۴٬۳٬۴٬۵]
با این راه حل ادغامی یک پرس و جو در زمان (O(log n + k انجام می‌شود. زمان Log n برای جستجوی q در لیست n تایی L، و k برای گزارش کردن نتایج صرف می‌شود. با توجه به اینکه مکان هایx در هر لیست‌های ورودی، در لیست L عنصر x ذخیره شده‌اند، نتایج پس از جستجو بدست می‌آیند.
این مدل، چنین مسئله‌های جستجویی را با صرف زمان (O(log n + kو حافظهٔ (O(n حل می‌کند. راه حل آبشاره‌سازی جزءبه‌جزء ذخیره کردن دنباله‌های جدیدی از لیست‌های Mi است. لیست نهایی در این دنباله Mk است که برابر است با Lk، و هر لیست قبلی از ادغام Li با هر یک از
به ازای هر عنصر x در این لیست ادغامی، ما دو عدد ذخیره می‌کنیم: مکانی که از جستجوی x در Li به دست می‌آید، و مکانی که از جستجوی x در Mi+۱ بدست می‌آید. به ازای داده‌های بالا، چنین عملی، این لیست‌ها را به ما می‌دهد:
M1 = ۲٫۴[۰، ۱], ۲٫۵[۱، ۱], ۳٫۵[۱، ۳], ۶٫۴[۱، ۵], ۶٫۵[۲، ۵], ۷٫۹[۳، ۵], ۸[۳، ۶], ۹٫۳[۴، ۶]
M2 = ۲٫۳[۰، ۱], ۲٫۵[۱، ۱], ۲٫۶[۲، ۱], ۳٫۵[۳، ۱], ۶٫۲[۳، ۳], ۷٫۹[۳، ۵]
M3 = ۱٫۳[۰، ۱], ۳٫۵[۱، ۱], ۴٫۴[۱، ۲], ۶٫۲[۲، ۳], ۶٫۶[۳، ۳], ۷٫۹[۴، ۳]
M4 = ۱٫۱[۰، ۰], ۳٫۵[۱، ۰], ۴٫۶[۲، ۰], ۷٫۹[۳، ۰], ۸٫۱[۴، ۰]
فرض کنید می‌خواهیم یک پرس و جو برای q=۵ انجام دهیم. ابتدا یک جستجوی دودویی به دنبال qدر M۱انجام می‌دهیم و مقدار ۶٫۴[۱٬۵]. را پیدا می‌کنیم. عدد «۱» در ۶٫۴[۱٬۵]. به ما می‌گوید که جستجوی q در L۱ باید L۱[۱] = ۶٫۴ را برگرداند. عدد ۵ نیز می‌گوید تخمین موقعیت q در M۲ مکان ۵ است. با دقت بیشتر، جستجوی دودویی برای q در M۲ مقدار ۷٫۹[۳، ۵] در موقعیت ۵ یا مقدار۶٫۲[۳، ۳] یک مکان جلوتر را برمی‌گرداند. در مقایسه q با ۶٫۲ و مشاهده اینکه کوچکتر است، ما می‌یابیم که نتیجه درست در M۲ , ۶٫۲[۳، ۳] است. اولین «۳» در ۶٫۲[۳، ۳] به ما می‌گوید که جستجو برای qدر L۲ باید L۲[۳] را برگرداند. یک مقدار پرچم به معنی آن است که q از انتهای لیست L۲ گذشته‌است. دومین «۳» در ۶٫۲[۳، ۳] به ما می‌گوید که تخمین موقعیت qدر M۳ موقعیت ۳ است. به طور دقیق تر، جستجوی دودویی برای q در M۳ مقدار۶٫۲[۲، ۳] در موقعیت ۳ یا مقدار ۴٫۴[۱، ۲] یک مکان جلوتر را برمی‌گرداند. در مقایسه q با مقدار کمتر ۶٫۲. به ما نشان می‌دهد که نتیجه درست در M۳ ،۶٫۲[۲٬۳] است. «۲» در۶٫۲[۲٬۳] به ما می‌گوید که جستجو برای qدر L۳ باید L۳[۲]=۶٫۲ را برگرداند و «۳» در ۶٫۲[۲٬۳] به ما می‌گوید که نتیجه جستجو برای q در M۴ برابر با M۴[۳] = ۷٫۹[۳٬۰] یا M۴[۲] = ۴٫۶[۲٬۰] است. با مقایسه q با ۴٫۶ نشان می‌دهد که نتیجه صحیح ۷٫۹[۳٬۰] است و نتیجه جستجو برای q در L۴ برابر L۴[۳] = ۷٫۹. است پس ما q را در هر یک از چهار لیست پیدا کردیم بوسیله جستجوی دوتایی در تک لیست M۱ همراه با یک مقایسه در هر لیست متواتر.
به‌طور کلی تر برای هر ساختار داده از این نوع ما یک پرس و جو را بوسیله انجام یک جستجوی دودویی q در M۱ انجام می‌دهیم و با استفاده از مقدار نتیجه شده موقعیتq در L۱ را تعیین می‌کنیم.
در مثال ما، لیست‌های آبشاره‌سازی جزءبه‌جزء شده، در مجموع ۲۵ عنصر دارند که مقداری کمتر از دو برابر ورودی اصلی است. به طور کلی سایز Mi در این داده ساختار حداکثر به این اندازه‌است:

Lj| + ½| Li + ۱ | + ¼ | Li + ۲ | + … + ۱/ ۲j | Mi + j | +….
که به سادگی اثبات می‌شود سایز داده ساختار حد اکثر ۲n است:
(Σ|Mi| = Σ|Li|(۱ + ½ + ¼ +…) ≤ ۲n = O(n