Staircase Patterns#4073

Staircase Patterns (Editorial)

The numbers written on the steps are integers and fall within the range from $0$ to $1 0^{6}$ 10^6 inclusive.

We will construct a Fenwick tree on an array $a$ of length $1 0^{6} + 1$ 10^6 + 1 (with indices ranging from $0$ to $1 0^{6}$ 10^6 inclusive), initially filled with zeros.

Each time the detective steps on a stair with the value $v a l u e$ , we increase $a_{v a l u e}$ a_{value} by $v a l u e$ . At the same time, he records the sum in his notebook:

a_{0} + a_{1} + a_{2} + ... + a_{v a l u e - 1}

a_0 + a_1 + a_2 + ... + a_{value - 1}

Given the input constraints, all calculations should be performed using a $64$ -bit integer type.

Example

Let's simulate the detective's recordings using the given example. The array indexing starts from $0$ . The numbers recorded by the detective are shown under the arrows.

The sum of the numbers written in the detective's notebook is

0 + 1 + 1 + 9 + 4 = 15

0 + 1 + 1 + 9 + 4 = 15

Algorithm implementation

Let the maximum array size be $M A X$ . Create a Fenwick tree $F e n w i c k$ Fenwick.

#define MAX 1000001
vector<long long> Fenwick;

The function Summa0_i computes the sum $a_{0} + a_{1} + ... + a_{i}$ a_0 + a_1 + ... + a_i.

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

C++

The function IncElement increases the value of an element: $a_{i} = a_{i} + d e l t a$ a_i = a_i + delta.

void IncElement(int i, int delta)
{
  for (; i < MAX; i = (i | (i+1)))
    Fenwick[i] += delta;
}

The main part of the program. Read the input data.

scanf("%d",&tests);
while (tests--)
{
  scanf("%d",&n);

Initialize the $F e n w i c k$ Fenwick array with zeros.

  Fenwick.assign(MAX,0);

The desired sum recorded in the detective's notebook will be computed in the variable $s u m$ .

  sum = 0;

Process the numbers written on the steps one by one.

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

For each $v a l u e$ , written on a step, increase $a_{v a l u e}$ a_{value} by $v a l u e$ and compute the sum of all previously encountered numbers smaller than $v a l u e$ . This sum is $a_{0} + a_{1} + a_{2} + ... + a_{v a l u e - 1}$ a_0 + a_1 + a_2 + ... + a_{value - 1}.

    scanf("%d",&value);
    IncElement(value, value);
    sum += Summma0_i(value - 1);
  }

Print the total sum of all numbers written in the detective's notebook.

  printf("%lld\n",sum);
}