يجب ألا يكون هناك بعض المصفوفة. في حالة عدم وجود تغييرات ، يمكننا بسرعة (أسرع من سطر) العثور على قيمة بعض الوظائف في جزء فرعي من هذه المصفوفة. للقيام بذلك ، نحتاج إلى استخدام ذاكرة إضافية وإجراء عملية حسابية مسبقة.
على سبيل المثال ، نحن بحاجة إلى إيجاد المجموع بسرعة في بعض أجزاء المصفوفة.
دعنا نحصل على مصفوفة من مجاميع البادئة ، حيث سيكون الفهرس i هو مجموع جميع عناصر المصفوفة التي تحتوي على مؤشرات أقل من أو تساوي i.
أ [] & - مجموعة معينة ، p [] & - مجموعة مجاميع البادئة
عدد الصفيف ص:
من الواضح أن p [0] = a [0]. لاحظ أنه يمكننا بسهولة إعادة حساب p [i] عبر p [i & ndash؛ 1] لأن المبلغ الموجود على البادئة i هو المبلغ الموجود على البادئة i & ndash؛ 1 + أ [i].
وبالتالي ، فإن الكود الخاص بحساب مجموع البادئات يبدو كما يلي:
int a [n]، p [n]؛
p [ 0 ] = a [ 0 < / span>]؛
لـ ( int i = 1 ؛ i & lt؛ n؛ i ++ )
p [i] = p [i - 1 ] + a [i]؛
علاوة على ذلك ، نلاحظ أن المجموع على القطعة - الفرق بين مجموعتي البادئة.
أخضر = أحمر & - أزرق
وبالتالي ، إذا كان من الضروري إيجاد المجموع في الفترة [l، r] ، فإن الإجابة هي p [r] & ndash؛ ص [ل -1].
ومع ذلك ، إذا l & ndash؛ قد لا يوجد عنصر واحد. من أجل الاستغناء عن if & rsquo ؛ s ، يمكنك إدخال 1-indexing ، وستكون لـ [0] و p [0] قيم محايدة (0 للمجموع).
نبسب ؛
لاحظ أن هذه التقنية هي حالة خاصة لصيغة التضمين والاستبعاد ، لذلك بهذه الطريقة يمكن تخزين ليس فقط المجاميع ، ولكن أيضًا وظائف أخرى ، مثل الضرب و xor.
نبسب ؛