2940. Дима и большой массив

 

Мама подарила мальчику Диме массив длины n. Массив этот не простой, а особенный. Дима может выбрать два числа i и d (1 ≤ i ≤ n, -1000 ≤ d ≤ 1000), и к элементу с индексом i магически прибавляется d. Дима играет со своим массивом, а мама время от времени задает ему вопросы – какова сумма всех чисел в массиве с индексами от f до t? Однако мама очень занята и не может задавать вопросы так часто, как обычно – всего она задала не более 1000 вопросов. Дима легко справился с этими вопросами, сможете ли Вы?

 

Вход. В первой строке находятся два целых числа n и q (1 ≤ n ≤ 106, 1 ≤ q ≤ 5·105) – количество элементов в массиве и суммарное количество операций и запросов соответственно. В следующей строке дано n чисел a1, a2, ..., an (−1000 ≤ ai ≤ 1000) – начальное состояние массива. В следующих q строках заданы операции и запросы. Первый символ в строке может быть + или ?. Если строка начинается с +, то это операция прибавления. Далее следуют i и d, ограничения на которые описаны в условии. Если строка начинается с ?, то это запрос. Далее следуют числа f и t (1 ≤ f, t ≤ n).

 

Выход. Для каждого запроса выведите сумму чисел в массиве с индексами от f до t, по одному результату в строке.

 

Пример входа

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

3 3

1 2 3

? 1 3

+ 3 -1

? 1 3

6

5

 

 

РЕШЕНИЕ

структуры данных – дерево Фенвика

 

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

В задаче необходимо реализовать только единичную модификацию. С учетом ограничения n ≤ 106, воспользуемся деревом Фенвика. Поскольку чисел в массиве не более 106, и каждое из них по модулю не больше 103, то сумма чисел на любом отрезке не превзойдет по модулю 109, достаточно использовать тип int.

Пусть функция sum(i) вычисляет сумму чисел a1 + a2 + ... + ai. Тогда запрос на отрезке [f; t] вычисляется как sum(t) – sum(f – 1).

SQRT декомпозиция в данной задаче работает дольше дерева Фенвика.

 

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

Дерево Фенвика храним в массиве Fenwick.

 

#define MAX 1000010

int Fenwick[MAX];

 

Функция Summa0_i возвращает сумму элементов a0 + a1 + ... + ai.

 

int Summma0_i(int i)

{

  int result = 0;

  for (; i >= 0; i = (i & (i + 1)) - 1)

    result += Fenwick[i];

  return result;

}

 

Функция IncElement измененяет элемент: ai = ai + delta.

 

 void IncElement(int i, int delta)

{

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

    Fenwick[i] += delta;

}

 

Основная часть программы. Читаем входные данные. Заполняем дерево Фенвика.

 

scanf("%d %d",&n,&q);

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

  scanf("%d",&value), IncElement(i,value);

scanf("\n");

 

Моделируем выполнение запросов.

 

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

{

  scanf("%c ",&c);

  if (c == '+')

  {

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

    IncElement(i,d);

  } else

  {

    scanf("%d %d\n",&f,&t);

    printf("%d\n",Summma0_i(t) - Summma0_i(f - 1));

  }

}

 

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

 

#include <cstdio>

#include <cmath>

#include <vector>

using namespace std;

 

vector<int> a, b;

int len, n, i, j, d, q, f, t;

char c;

 

void BuildSQRT(vector<int> &a, vector<int> &b)

{

  len = sqrt(n) + 1;

  b.resize(len);

  for (int i = 0; i < n; i++)

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

}

 

int sum(int l, int r)

{

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

}

 

void update(int pos, int value)

{

  a[pos] += value;

  b[pos / len] += value;

}

 

int main(void)

{

  scanf("%d %d", &n, &q);

  a.resize(n);

  for (i = 0; i < n; i++)

    scanf("%d", &a[i]);

  scanf("\n");

 

  BuildSQRT(a, b);

 

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

  {

    scanf("%c ", &c);

    if (c == '+')

    {

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

      i--;

      update(i, d);

    }

    else

    {

      scanf("%d %d\n", &f, &t);

      f--; t--;

      printf("%d\n", sum(f, t));

    }

  }

  return 0;

}

 

Java реализация

 

import java.util.*;

 

public class Main

{

  static int Fenwick[];

  final static int MAX = 1000001;

 

  static int Summma0_i(int i)

  {

    int result = 0;

    for (; i >= 0; i = (i & (i + 1)) - 1)

      result += Fenwick[i];

    return result;

  }

 

  static void IncElement(int i, int delta)

  {

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

      Fenwick[i] += delta;

  }

 

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    int n = con.nextInt();

    int q = con.nextInt();

    Fenwick = new int[MAX];

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

    {

      int val = con.nextInt();

      IncElement(i,val);

    }

   

    for(int j = 0; j < q; j++)

    {

      char c = con.next().charAt(0);

      if (c == '+')

      {

        int i = con.nextInt();

        int d = con.nextInt();

        IncElement(i,d);

      } else

      {

        int f = con.nextInt();

        int t = con.nextInt();

        System.out.println(Summma0_i(t) - Summma0_i(f - 1));

      }

    }

    con.close();

  }

}

 

Python реализация

 

Fenwick = []

 

def Summma0_x(i):

  s = 0

  while i >= 0:

    s += Fenwick[i]

    i = (i & (i + 1)) – 1

  return s

 

def IncElement(i, delta):

  while i <= n:

    Fenwick[i] += delta

    i = i | (i + 1)

 

n, q = map(int,input().split())

lst = [0] + list(map(int,input().split()))

Fenwick = [0] * (n+1)

for i in range(1,n+1):

  IncElement(i, lst[i])

 

for i in range(q):

  l = input().split()

  if l[0] == '+':

    IncElement(int(l[1]), int(l[2]))

  else:

    print(Summma0_x(int(l[2])) - Summma0_x(int(l[1]) - 1))