لدينا مشكلة حول كيفية حساب المجاميع بسرعة على الفاصل الزمني l ... r في مصفوفة ثابتة a في أقل من O (n) مقارب.
دعنا نقسم المصفوفة a إلى كتل k من نفس الحجم ونحسب أولاً مجموع العناصر لكل منها.
الآن ، عند الإجابة على الطلب ، يمكننا استعراض عناصر المصفوفة a وإضافتها إلى النتيجة ، أيضًا إذا كانت إحدى الكتل موجودة داخل المقطع ، فيمكننا إضافة مجموعها إلى النتيجة وتخطي عناصر هذه الكتلة.
الحد الأقصى لعدد العمليات لكل استعلام بهذه الخوارزمية هو n / k + k ، وبالتالي فإن k الأمثل يساوي الجذر التربيعي لـ n.
& nbsp؛
|
لدينا مشكلة حول كيفية حساب المجاميع على المقطع l ... r في المصفوفة a بسرعة ، حيث يمكن للعناصر أن تتغير واحدة تلو الأخرى ، في مقاربات أقل من O (n).
يتم حل هذه المهمة بشكل مشابه للمهمة السابقة ، ولكن عند طلب التغيير ، تحتاج إلى تغيير المبلغ في الكتلة المقابلة.
|
مهمة معطاة يكون من الضروري فيها تنفيذ عمليات مجمعة على مقطع ما والتعرف على عنصر بفهرس.
يتم تنفيذ العمليات الجماعية كحساب مجموع على مقطع.
لكل كتلة ، نقوم بتخزين التغيير في تلك الكتلة ، وعند طلب عنصر من تلك الكتلة ، نأخذ هذه المعلومات في الاعتبار.
|