#26. Binary Indexed Tree (Fenwick)
Sizga barcha elementlari nolga teng bo'lgan (yoki boshlang'ich qiymatlari berilgan) n uzunlikdagi A massivi berilgan. Siz ushbu massiv ustida quyidagi q ta so'rovni bajarishingiz kerak:
1 i x — Massivning i-indeksdagi elementiga x qiymatini qo'shish (A[i] = A[i] + x).
2 l r — Massivning l-indeksdan r-indeksgacha bo'lgan barcha elementlari yig'indisini hisoblash.
Birinchi qatorda n va q. Ikkinchi qatorda massivning boshlang'ich elementlari kiritiladi. Keyingi q ta qatorda yuqoridagi 1 yoki 2 turdagi so'rovlar kiritiladi.
Har bir 2-tur so'rovi uchun oraliq yig'indisini alohida qatorda chiqaring.
n ≤ 2×10⁵
You are given an array A of length n, where all elements are initially equal to zero. You need to perform q queries on this array:
1 i x — Add the value x to the element at the i-th index of the array (A[i] = A[i] + x).
2 l r — Calculate the sum of all elements of the array from the l-th index to the r-th index.
The first line contains n and q. The second line contains the initial elements of the array. The next q lines contain queries of type 1 or 2 as described above.
For each query of type 2, output the range sum on a new line.
n ≤ 2×10⁵
Вам дан массив A длины n, все элементы которого изначально равны нулю. Вам необходимо выполнить q запросов к этому массиву:
1 i x — Прибавить значение x к элементу по индексу i в массиве (A[i] = A[i] + x).
2 l r — Вычислить сумму всех элементов массива от l-го до r-го индекса.
В первой строке заданы n и q. Во второй строке заданы начальные элементы массива. В следующих q строках заданы запросы 1-го или 2-го типа, как описано выше.
Для каждого запроса 2-го типа выведите сумму на отрезке в отдельной строке.
n ≤ 2×10⁵
Sizga barcha elementlari nolga teng bo'lgan (yoki boshlang'ich qiymatlari berilgan) n uzunlikdagi A massivi berilgan. Siz ushbu massiv ustida quyidagi q ta so'rovni bajarishingiz kerak:
1 i x — Massivning i-indeksdagi elementiga x qiymatini qo'shish (A[i] = A[i] + x).
2 l r — Massivning l-indeksdan r-indeksgacha bo'lgan barcha elementlari yig'indisini hisoblash.
Kiruvchi ma'lumotlar
Birinchi qatorda n va q. Ikkinchi qatorda massivning boshlang'ich elementlari kiritiladi. Keyingi q ta qatorda yuqoridagi 1 yoki 2 turdagi so'rovlar kiritiladi.
Chiquvchi ma'lumotlar
Har bir 2-tur so'rovi uchun oraliq yig'indisini alohida qatorda chiqaring.
Cheklovlar
n ≤ 2×10⁵
Misollar
3 2 1 2 3 2 1 3 1 1 10
6