Сума на відрізку (Розбір)

У задачі потрібно обробляти запити двох типів: присвоєння значення одному елементу масиву та обчислення суми елементів на відрізку $[l; r]$ [l; r]. Якщо зберігати лише сам масив, присвоєння виконується за $O (1)$ , але кожен запит суми потребує $O (n)$ операцій. Якщо зберігати префіксні суми, сума обчислюється за $O (1)$ , але кожне присвоєння вимагає перерахунку $O (n)$ префіксних сум. При великій кількості запитів обидва підходи є занадто повільними.

Використаємо дерево відрізків для сум. Кожна його вершина зберігає суму елементів свого відрізка, причому значення у внутрішній вершині дорівнює сумі значень її двох дітей. Дерево відрізків виконує обидві операції за $O (lo g n)$ O(\log n). При обчисленні суми порожня частина відрізка відповідає $0$ — нейтральному елементу для додавання.

Спочатку всі елементи масиву дорівнюють нулю, тому суми в усіх вершинах дерева також дорівнюють нулю. Достатньо заповнити масив дерева нулями; окрема побудова дерева не потрібна.

Значення елементів досягають $1 0^{9}$ 10^9, тому сума на відрізку може досягати $1 0^{5} \cdot 1 0^{9} = 1 0^{14}$ 10^5 \cdot 10^9 = 10^{14} і не вміщується в тип int. Значення в дереві зберігаються в типі long long.

Розглянемо розв'язок із використанням дерева Фенвіка. Воно підтримує дві операції, кожна з яких виконується за $O (lo g n)$ O(\log n):

додавання числа $d e l t a$ до елемента $a_{i}$ a_i;
обчислення префіксної суми $s u m (i) = a_{0} + a_{1} + \dots + a_{i}$ sum(i) = a_0 + a_1 + \ldots + a_i.

Спочатку всі елементи масиву дорівнюють нулю, тому дерево Фенвіка, заповнене нулями, вже відповідає початковому масиву. Індекси в запитах змінюються від $1$ до $n$ ; елемент $a_{0}$ a_0 не використовується і завжди дорівнює нулю.

Присвоєння. Дерево Фенвіка може лише додавати число до елемента, але не може присвоїти йому нове значення. Однак поточне значення елемента можна обчислити через префіксні суми:

a_{i} = s u m (i) - s u m (i - 1)

a_i = sum(i) - sum(i - 1)

Тому присвоєння $a_{i} = x$ a_i = x замінюється на додавання до $a_{i}$ a_i різниці між новим і старим значеннями:

d e l t a = x - (s u m (i) - s u m (i - 1)) = x - s u m (i) + s u m (i - 1)

delta = x - (sum(i) - sum(i - 1)) = x - sum(i) + sum(i - 1)

Сума на відрізку. Сума елементів на відрізку $[l; r]$ [l; r] дорівнює різниці двох префіксних сум:

a_{l} + a_{l + 1} + \dots + a_{r} = s u m (r) - s u m (l - 1)

a_l + a_{l+1} + \ldots + a_r = sum(r) - sum(l - 1)

Значення елементів досягають $1 0^{9}$ 10^9, тому суми можуть досягати $1 0^{14}$ 10^{14} і зберігаються в типі long long.

Приклад

Спочатку масив складається з нулів. Після запитів $A 22$ , $A 31$ і $A 42$ масив стає $(0, 2, 1, 2, 0)$ (0, 2, 1, 2, 0). Дерево відрізків для нього показано нижче. У кожній вершині показано її відрізок і суму елементів на ньому.

При виконанні запиту $A 31$ перераховуються лише вершини на шляху від листка $[3]$ до кореня: листок $[3]$ отримує значення $1$ , вершина $[1; 3]$ — значення $2 + 1 = 3$ 2 + 1 = 3, а корінь $[1; 5]$ — значення $3 + 2 = 5$ 3 + 2 = 5.

Запити $Q 11$ , $Q 22$ , $Q 33$ , $Q 44$ і $Q 55$ повертають значення листків: $0, 2, 1, 2, 0$ 0, 2, 1, 2, 0. Відрізок запиту $Q 15$ збігається з відрізком кореня, тому відповідь береться безпосередньо з кореня і дорівнює $5$ (виділена вершина).

Просимулюємо запити з прикладу за допомогою дерева Фенвіка, $n = 5$ n = 5. Спочатку масив $(0, 0, 0, 0, 0)$ (0, 0, 0, 0, 0). Для кожного запиту присвоєння в таблиці показано, як обчислюється старе значення елемента і яке число додається; для кожного запиту суми показано різницю префіксних сум.

запит	обчислення	результат
$A 22$	старе значення $s u m (2) - s u m (1) = 0 - 0 = 0$ sum(2) - sum(1) = 0 - 0 = 0, додаємо $2 - 0 = 2$ 2 - 0 = 2	$(0, 2, 0, 0, 0)$ (0, 2, 0, 0, 0)
$A 31$	старе значення $s u m (3) - s u m (2) = 2 - 2 = 0$ sum(3) - sum(2) = 2 - 2 = 0, додаємо $1 - 0 = 1$ 1 - 0 = 1	$(0, 2, 1, 0, 0)$ (0, 2, 1, 0, 0)
$A 42$	старе значення $s u m (4) - s u m (3) = 3 - 3 = 0$ sum(4) - sum(3) = 3 - 3 = 0, додаємо $2 - 0 = 2$ 2 - 0 = 2	$(0, 2, 1, 2, 0)$ (0, 2, 1, 2, 0)
$Q 11$	$s u m (1) - s u m (0) = 0 - 0$ sum(1) - sum(0) = 0 - 0	$0$
$Q 22$	$s u m (2) - s u m (1) = 2 - 0$ sum(2) - sum(1) = 2 - 0	$2$
$Q 33$	$s u m (3) - s u m (2) = 3 - 2$ sum(3) - sum(2) = 3 - 2	$1$
$Q 44$	$s u m (4) - s u m (3) = 5 - 3$ sum(4) - sum(3) = 5 - 3	$2$
$Q 55$	$s u m (5) - s u m (4) = 5 - 5$ sum(5) - sum(4) = 5 - 5	$0$
$Q 15$	$s u m (5) - s u m (0) = 5 - 0$ sum(5) - sum(0) = 5 - 0	$5$

Наприклад, перед запитом $Q 44$ масив $(0, 2, 1, 2, 0)$ (0, 2, 1, 2, 0), тому $s u m (4) = 0 + 2 + 1 + 2 = 5$ sum(4) = 0 + 2 + 1 + 2 = 5, $s u m (3) = 0 + 2 + 1 = 3$ sum(3) = 0 + 2 + 1 = 3, і відповідь дорівнює $5 - 3 = 2$ 5 - 3 = 2.

У прикладі всі присвоєння застосовуються до нульових елементів. Подивимось, що відбудеться при повторному присвоєнні, наприклад $A 35$ наприкінці. Старе значення дорівнює $s u m (3) - s u m (2) = 3 - 2 = 1$ sum(3) - sum(2) = 3 - 2 = 1, тому до $a_{3}$ a_3 додається $5 - 1 = 4$ 5 - 1 = 4, і елемент стає рівним $5$ .

Реалізація алгоритму

Дерево відрізків зберігається в масиві $S e g T r ee$ SegTree довжиною $4 \cdot M A X$ 4 \cdot MAX, де $M A X$ — максимальна кількість елементів масиву. Сума на відрізку може перевищувати межі типу int, тому значення в дереві мають тип long long.

#define MAX 100010
long long SegTree[4 * MAX];

Функція Summa повертає суму елементів на відрізку $[l e f t; r i g h t]$ [left; right]. Вершина $v$ відповідає відрізку $[l p os; r p os]$ [lpos; rpos].

long long Summa(int v, int lpos, int rpos, int left, int right)
{

Якщо запитуваний відрізок порожній ( $l e f t > r i g h t$ left > right), повертаємо $0$ — нейтральний елемент для додавання.

  if (left > right) return 0;

Якщо запитуваний відрізок збігається з відрізком $[l p os; r p os]$ [lpos; rpos] вершини $v$ , повертаємо суму, що зберігається в ній.

  if ((left == lpos) && (right == rpos))
    return SegTree[v];

Інакше знаходимо середину відрізка $mi d = (l p os + r p os) /2$ mid = (lpos + rpos) / 2.

  int mid = (lpos + rpos) / 2;

Розбиваємо запитуваний відрізок на дві частини: $[l e f t; min (r i g h t, mi d)]$ [left; \min(right, mid)] лежить у відрізку лівого нащадка, а $[max (l e f t, mi d + 1); r i g h t]$ [\max(left, mid + 1); right] — у відрізку правого нащадка. Одна з частин може бути порожньою. Рекурсивно обчислюємо суми на обох частинах і повертаємо їхню суму.

  return Summa(2*v, lpos, mid, left, min(right, mid)) +
         Summa(2*v+1, mid + 1, rpos, max(left, mid + 1), right);
}

Функція update присвоює значення $v a l$ елементу з індексом $p os$ . Вершина $v$ відповідає відрізку $[l p os; r p os]$ [lpos; rpos].

void update(int v, int lpos, int rpos, int pos, int val)
{

Якщо відрізок вершини $v$ складається з одного елемента ( $l p os = r p os$ lpos = rpos), то $v$ — це листок, що відповідає позиції $p os$ . Записуємо в нього значення $v a l$ .

  if (lpos == rpos)
    SegTree[v] = val;
  else
  {

Інакше визначаємо, яка половина відрізка містить позицію $p os$ , і рекурсивно спускаємось у лівого або правого нащадка.

    int mid = (lpos + rpos) / 2;
    if (pos <= mid) update(2*v, lpos, mid, pos, val);
    else update(2*v+1, mid + 1, rpos, pos, val);

Після повернення з рекурсії перераховуємо суму у вершині $v$ . Таким чином оновлюються всі вершини на шляху від листка до кореня.

    SegTree[v] = SegTree[2*v] + SegTree[2*v+1];
  }
}

Основна частина програми. Спочатку всі елементи масиву дорівнюють нулю, тому всі суми в дереві відрізків також дорівнюють нулю. Заповнюємо масив $S e g T r ee$ SegTree нулями; окрема побудова дерева не потрібна.

memset(SegTree, 0, sizeof(SegTree));

Зчитуємо розмір масиву $n$ і кількість запитів $k$ . Символ \n у форматі пропускає перехід на новий рядок, щоб наступним символом, який зчитується, була буква запиту.

scanf("%d %d\n", &n, &k);

Обробляємо $k$ запитів по черзі. Спочатку зчитуємо букву запиту $co mman d$ . Якщо вона дорівнює 'A', присвоюємо значення $x$ елементу з індексом $i$ . Інакше виводимо суму на відрізку $[l; r]$ [l; r]. Символ \n у форматі "%lld %lld\n" пропускає перехід на новий рядок після запиту.

for (j = 0; j < k; j++)
{
  scanf("%c", &command);
  if (command == 'A')
  {
    scanf("%lld %lld\n", &i, &x);
    update(1, 1, n, i, x);
  }
  else
  {
    scanf("%lld %lld\n", &l, &r);
    printf("%lld\n", Summa(1, 1, n, l, r));
  }
}

C++

Реалізація алгоритму — дерево Фенвіка

Масив $F e n w i c k$ Fenwick розміру $M A X$ зберігає дерево Фенвіка. Глобальний масив спочатку заповнений нулями, що відповідає початковому нульовому масиву.

#define MAX 100010
long long Fenwick[MAX];

Функція Summma0_i повертає префіксну суму $s u m (i) = a_{0} + a_{1} + \dots + a_{i}$ sum(i) = a_0 + a_1 + \ldots + a_i.

// Fenwick[0] + Fenwick[1] + ... + Fenwick[i]
long long Summma0_i(long long i)
{
  long long result = 0;
  for (; i >= 0; i = (i & (i + 1)) - 1)
    result += Fenwick[i];
  return result;
}

C++

Функція IncElement додає $d e l t a$ до елемента $a_{i}$ a_i. Індекси елементів змінюються від $1$ до $n$ , тому цикл виконується, поки $i \leq n$ i \le n.

// Fenwick[i] = Fenwick[i] + delta
void IncElement(long long i, long long delta)
{
  for (; i <= n; i = (i | (i+1)))
    Fenwick[i] += delta;
}

Основна частина програми. Зчитуємо розмір масиву $n$ і кількість запитів $k$ . Символ \n у форматі пропускає перехід на новий рядок, щоб наступним символом, який зчитується, була буква запиту.

scanf("%d %d\n",&n,&k);

Обробляємо $k$ запитів по черзі. Спочатку зчитуємо букву запиту $co mman d$ .

for(j = 0; j < k; j++)
{
  scanf("%c",&command);

Запит $A i x$ . Поточне значення елемента $a_{i}$ a_i дорівнює $s u m (i) - s u m (i - 1)$ sum(i) - sum(i - 1). Щоб присвоїти йому значення $x$ , замінюємо $x$ на різницю $x - s u m (i) + s u m (i - 1)$ x - sum(i) + sum(i - 1) і додаємо її до $a_{i}$ a_i за допомогою функції IncElement.

  if (command == 'A')
  {
    scanf("%lld %lld\n",&i,&x);
    x = x - Summma0_i(i) + Summma0_i(i-1);
    IncElement(i,x);

Запит $Q l r$ . Сума на відрізку $[l; r]$ [l; r] дорівнює $s u m (r) - s u m (l - 1)$ sum(r) - sum(l - 1).

  } else
  {
    scanf("%lld %lld\n",&l,&r);
    printf("%lld\n",Summma0_i(r) - Summma0_i(l-1));
  }
}