4255. Сумма на отрезке

 

Дан массив из n чисел. Найдите сумму чисел на отрезке.

 

Вход. Первая строка содержит два целых числа n и k – количество чисел в массиве и количество запросов (1 ≤ n ≤ 105, 0 ≤ k ≤ 105). Следующие k строк содержат запросы двух типов:

·        A i x – присвоить i-му элементу массива значение x (1 ≤ i ≤ n, 0 ≤ x ≤ 109);

·        Q l r – найти сумму чисел в массиве на позициях от l до r (1 ≤ l ≤ r ≤ n).

Изначально в массиве находятся нули.

 

Выход. На каждый запрос вида Q l r вывести сумму чисел на отрезке [l; r].

 

Пример входа

Пример выхода

5 9

A 2 2

A 3 1

A 4 2

Q 1 1

Q 2 2

Q 3 3

Q 4 4

Q 5 5

Q 1 5

0

2

1

2

0

5

 

 

РЕШЕНИЕ

дерево отрезков, дерево Фенвика

 

Анализ алгоритма

Решение при помощи дерева Фенвика. Пусть a – массив длины 105 + 1, который изначально содержит все нули (индексы в запросах изменяются от 1 до 105). Построим по нем дерево Фенвика Fenwick. Поскольку индексы в запросах изменяются от 1 до n, то в функции IncElement цикл по i следует совершать до n включительно.

Рассмотрим реализацию операции ai = x, Дерево Фенвика способно только прибавлять число к ai, но не изменять его. Пусть x‘ – значение, которое содержит ai до выполнения операции. Тогда присваивание ai = x можно заменить на добавление к ai значения x – x’. В то же время x‘ можно вычислить как sum(i) – sum(i – 1) (от суммы чисел на интервале a[0..i] отняли сумму чисел на интервале a[0..i – 1]). То есть операцию присваивания ai = x мы заменили на добавление к ai значения x – sum(i) + sum(i – 1).

Сумма чисел на отрезке a[l; r] равна sum(r) – sum(l – 1).

 

Задачу также можно решить при помощи дерева отрезков.

 

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

Дерево отрезков храним в массиве SegTree длины 4*MAX, где MAX – максимальное количество элементов, которое может храниться в отрезке.

 

#define MAX 100010

long long SegTree[4 * MAX];

 

Функция Summa возвращает значение суммы на отрезке [left; right].

Вершине v соответствует отрезок [lpos; rpos].

 

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

{

  if (left > right) return 0;

 

Если отрезок [left; right] совпадает с отрезком [lpos; rpos], который хранится в вершине v дерева, то возвращаем находящееся в ней значение суммы.

 

  if ((left == lpos) && (right == rpos))

    return SegTree[v];

 

Находим середину отрезка mid = (lpos + rpos) / 2.

 

  int mid = (lpos + rpos) / 2;

 

Разбиваем отрезок [left; right] на [left; mid] и [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 присваивает элементу с индексом pos значение val.

Вершине v соответствует отрезок [lpos; rpos].

 

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

{

 

Если вершине v соответствует отрезок, состоящий из одного элемента (lpos = rpos), то мы дошли до листа дерева отрезков. Присваиваем ему значение val.

 

  if (lpos == rpos)

    SegTree[v] = val;

  else

  {

 

Иначе вычисляем, в каком – левом или правом сыне вершины v лежит элемент с индексом pos. Запускаем рекурсивно его модификацию.

 

    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);

 

Пересчитываем значение суммы в текущей вершине дерева отрезков.

 

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

  }

}

 

Основная часть программы. Изначально во входном массиве находятся нули.

 

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

 

Читаем входные данные.

 

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

 

Последовательно обрабатываем k запросов. В зависимости от типа запроса производим либо присваивание значения элементу, либо вычисление суммы на отрезке.

 

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));

  }

}

 

Реализация алгоритма - Фенвик

 

#include <stdio.h>

#define MAX 100010

 

long long Fenwick[MAX];

int n, k;

long long i, j, l, r, x;

char command;

 

// 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;

}

 

// Fenwick[i] = Fenwick[i] + delta

void IncElement(long long i, long long delta)

{

  for (; i <= n; i = (i | (i+1)))

    Fenwick[i] += delta;

}

 

int main (void)

{

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

  for(j = 0; j < k; j++)

  {

    scanf("%c",&command);

    if (command == 'A')

    {

      scanf("%lld %lld\n",&i,&x);

      x = x - Summma0_i(i) + Summma0_i(i-1);

      IncElement(i,x);

    } else

    {

      scanf("%lld %lld\n",&l,&r);

      printf("%lld\n",Summma0_i(r) - Summma0_i(l-1));

    }

  }

  return 0;

}

 

Реализация алгоритма – SQRT декомпозиция

 

#include <cstdio>

#include <cmath>

#include <vector>

using namespace std;

 

vector<long long> a, b;

int len, n, k, i, j, l, r, x;

char command;

 

long long q(int l, int r)

{

  long long sum = 0;

  int i, c_l = l / len, c_r = r / len;

  if (c_l == c_r)

    for (i = l; i <= r; i++)

      sum += a[i];

  else

  {

    for (i = l; i <= (c_l + 1)*len - 1; i++)

      sum += a[i];

    for (i = c_l + 1; i <= c_r - 1; i++)

      sum += b[i];

    for (i = c_r * len; i <= r; i++)

      sum += a[i];

  }

  return sum;

}

 

int main(void)

{

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

  a.resize(n);

  len = sqrt(n) + 1;

  b.resize(len);

 

  for (j = 0; j < k; j++)

  {

    scanf("%c", &command);

    if (command == 'A')

    {

      scanf("%d %d\n", &i, &x); i--;

      b[i / len] = b[i / len] + x - a[i];

      a[i] = x;

    }

    else

    {

      scanf("%d %d\n", &l, &r);

      printf("%lld\n", q(l - 1, r - 1));

    }

  }

  return 0;

}