لدينا مشكلة حول كيفية حساب المجاميع على المقطع l ... r في المصفوفة a بسرعة ، حيث يمكن للعناصر أن تتغير واحدة تلو الأخرى ، في مقاربات أقل من O (n).
يتم حل هذه المهمة بشكل مشابه للمهمة السابقة ، ولكن عند طلب التغيير ، تحتاج إلى تغيير المبلغ في الكتلة المقابلة.
Problem
إعطاء صفيف بطول n ( \ (1 & lt؛ = n & lt؛ = 2 \ cdot 10 ^ 6 \ ) ، \ (1 & lt؛ = a_i & lt؛ = 10 ^ 9 \) ). قدم أيضًا m ( \ (1 & lt؛ = m & lt؛ = 500 \) ) طلبات بحث مثل t ، l ، r ( \ (0 & lt؛ = t & lt؛ = 1 \) ، \ (1 & lt؛ = l & lt؛ = r & lt؛ = n \) ).
إذا \ (t = 0 \) ، فيجب أن يعرض طلب البحث مجموع الأرقام في المقطع من l إلى r شاملًا. إذا \ (t = 1 \) ، فسيتم تعيين رقم العنصر l على r . & nbsp؛ يتم تعيين العناصر مرقمة من 1 إلى n . & nbsp؛
نبسب ؛
أمثلة
| # |
إدخال |
الإخراج |
<الجسم>
| 1 |
5
1 2 3 4 5
4
0 1 2
1 1 5
0 1 2
0 1 1
|
3
7
5 |