The sum#2307

The sum (Editorial)

To solve the problem, it is necessary to implement a segment tree that supports range operations — assignment and summation.

In each node of the tree, the variable $a dd$ stores the value assigned to all elements of the segment corresponding to that node. If a node represents the segment $[l; r]$ [l; r], then the sum of the elements on this segment is equal to $a dd \cdot (r - l + 1)$ add \cdot (r - l + 1).

When performing assignment and summation operations, while descending the tree from the root to the leaves, the value of $a dd$ in each node must be pushed down to the next level of the tree.

When an assignment operation is performed, the previous sum values in the child nodes $s_{1}$ s_1 and $s_{2}$ s_2, as well as the pending assignment values $a_{1}$ a_1 and $a_{2}$ a_2, are discarded.

During the construction of the segment tree, the variable $a dd$ in each node is initialized with a value that will never be assigned to the elements of any segment (for example, $- 1$ ).

Algorithm implementation

The segment tree is stored as an array $S e g T r ee$ SegTree, whose elements are of type $n o d e$ . Each node of the tree corresponds to a certain segment of the array and stores information about that segment.

The $n o d e$ structure contains two fields:

$s u m$ — the sum of the elements on the corresponding segment;
$a dd$ — the value of the pending assignment (lazy propagation).

The constructor is called automatically when each node of the tree is created:

$s u m$ is initialized to zero, since at the construction stage the node does not yet contain any accumulated information about element values;
$a dd$ is initialized to $- 1$ , which is used as a special marker indicating the absence of a pending assignment. It is assumed that this value will never be actually assigned to elements of the array.

struct node
{
  long long sum, add;
  node() : sum(0), add(-1) {}
};
vector<node> SegTree;

The function Push propagates the value $a dd$ from node $v$ to its child nodes. If $a dd \neq = - 1$ add \ne -1, this value must be pushed down one level in the tree. After the propagation is completed, the value of $a dd$ in node $v$ is set to $- 1$ .

void Push(int v, int lpos, int mid, int rpos)
{

If $a dd = - 1$ add = -1, then there is no pending operation in node $v$ .

  if (SegTree[v].add == -1) return;

Recompute the values of $a dd$ and $s u m$ in the child nodes of node $v$ .

  SegTree[2*v].add = SegTree[v].add;
  SegTree[2*v].sum = (mid - lpos + 1) * SegTree[v].add;
  SegTree[2*v+1].add = SegTree[v].add;
  SegTree[2*v+1].sum = (rpos - mid) * SegTree[v].add;

After the propagation is completed, set $a dd = - 1$ add = -1 in node $v$ .

  SegTree[v].add = -1;
}

The function SetValue assigns the value $v a l$ to all elements in the segment $[l e f t; r i g h t]$ [left; right]. Node $v$ corresponds to the segment $[l p os; r p os]$ [lpos; rpos].

void SetValue(int v, int lpos, int rpos, int left, int right, int val)
{
    if (left > right) return;

If the segment $[l e f t; r i g h t]$ [left; right] corresponds to the segment $[l p os; r p os]$ [lpos; rpos] stored in the tree node, then we assign the appropriate values to the variables $a dd$ and $s u m$ in this node.

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

    SegTree[v].add = val;
    SegTree[v].sum = (long long)(right - left + 1) * val;
    return;
  }

C++

Find the midpoint of the segment: $mi d = (l p os + r p os) /2$ mid = (lpos + rpos) / 2.

  int mid = (lpos + rpos) / 2;

Perform propagation if $a dd$ is not equal to $- 1$ .

  Push(v, lpos, mid, rpos);

Recursively process the left and right child nodes of the current segment tree node.

  SetValue(2*v, lpos, mid, left, min(mid, right), val);
  SetValue(2*v+1, mid+1, rpos, max(left, mid+1), right, val);

Recompute the sum value in node $v$ using the sum values of its children.

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

The function Summa returns the sum of the elements in the segment $[l e f t; r i g h t]$ [left; right].Node $v$ corresponds to the segment $[l p os; r p os]$ [lpos; rpos].

long long Summa(int v, int lpos, int rpos, int left, int right)
{
  if (left > right) return 0;

If the segment $[l e f t; r i g h t]$ [left; right] coincides with the segment $[l p os; r p os]$ [lpos; rpos] stored in node $v$ of the tree, return the sum value stored in this node.

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

Find the midpoint of the segment: $mi d = (l p os + r p os) /2$ mid = (lpos + rpos) / 2.

  int mid = (lpos + rpos) / 2;

Perform propagation if $a dd$ is not equal to $- 1$ .

  Push(v, lpos, mid, rpos);

Split the segment $[l p os; r p os]$ [lpos; rpos] into two subsegments: $[l p os; mi d]$ [lpos; mid] and $[mi d + 1; r p os]$ [mid + 1; rpos]. Recursively compute the sums on these subsegments and add the obtained values.

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

The main part of the program. Read the input data and initialize the segment tree.

cin >> n >> k;
SegTree.resize(4 * n);

Process $k$ queries. Depending on the type of query, we either perform a range assignment or compute the sum over the specified segment.

while (k--)
{
  cin >> c;
  if (c == 'A')
  {
    cin >> l >> r >> x;
    SetValue(1, 1, n, l, r, x);
  }
  else
  {
    cin >> l >> r;
    cout << Summa(1, 1, n, l, r) << endl;
  }
}

C++