The array of [latex]n[/latex] elements is given. Find the sum of numbers on a segment.
Input
The first line contains two integers [latex]n[/latex] and [latex]k[/latex] [latex](1 \le n \le 10^5, 0 \le k \le 10^5)[/latex] — the number of elements in array and the number of queries. The next [latex]k[/latex] lines contain the queries of two forms:
- [latex]A[/latex] [latex]l[/latex] [latex]r[/latex] [latex]x[/latex] — assign the value of [latex]x[/latex] to each element form position [latex]l[/latex] to [latex]r[/latex] [latex](1 \le l \le r \le n, 0 \le x \le 10^9)[/latex]
- [latex]Q[/latex] [latex]l[/latex] [latex]r[/latex] — find the sum of array elements on positions from [latex]l[/latex] to [latex]r[/latex] [latex](1 \le l \le r \le n)[/latex]
Initially the array is filled with zeroes.
Output
For each query of the form «[latex]Q[/latex] [latex]l[/latex] [latex]r[/latex]» print the sum of numbers on a segment.
Tests
| № | Input | Output |
| 1 | 5 9 A 2 3 2 A 3 5 1 A 4 5 2 Q 1 3 Q 2 2 Q 3 4 Q 4 5 Q 5 5 Q 1 5 |
3 2 3 4 2 7 |
| 2 | 10 6 A 1 10 1 Q 1 10 A 1 5 2 Q 1 10 A 4 7 3 Q 1 10 |
10 15 21 |
| 3 | 100000 2 A 1 100000 1000000000 Q 1 100000 |
100000000000000 |
Algorithm
After reading the statement of the problem it is understandable that we should implement segment tree with support for multiple modification request — assignment. To make modifications to the whole segment and quickly answer for the amounts queries, we organize data structure in which each node store «colored» — if it is painted in any color or not and a sum on corresponding to this node segment.
|
1 2 3 4 |
struct Node { int color; long long sumOnSegment; }; |
Under the node coloring we will understand that all segment with all its subsegments should be colored in the appropriate color (assigned a specific number). Also define the mark that the node isn’t colored (in the code defined as WHITE), for example, any negative number, because queries contain only positive. This implementation allows us to do «delayed» update of the tree. Specifically, for each request of modification, instead of changing the values at all vertices where it is required, change only some of them, leaving «colored» markers for the other segments, which means that the whole segment with its subsegments should be painted in this color.
But if we do it so, after each modification request segment tree will stop being up to date. For resolving this problem, organise a function, that will «push» information from parents to children:
void push(Node *tree, int currentNode, int left, int right) . This function is called during requests processing to update the appropriate values:
- assign parent’s color to the children
- recalculate the amount of the segment for children (as the length of the segment multiplied by the current color (number))
- set parent node as uncolored
Thus, to solve this task, we need two usual for segment tree functions:
- void update(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder, int color)
- long long sum(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder)
With the difference that, when we are going down by the tree, pushes information only as far as necessary (it should be noted, that in this way the asymptotic doesn’t impair and remains standard [latex]O(\log n)[/latex]).
Rest details of the implementation can be found in the code of the program or in the sources of information listed at the end of the article.
Footnote: such realization, where the problem constraints too large queries, and in the current version when we update a range and only mark its child that it needs to be updated and update it when needed, usually calls lazy propagation. This approach allows us to solve a variety of new at first glance seemed complex tasks. More information listed at the end of the article.
Code
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 |
#include <cmath> #include <iostream> #define WHITE -1 using namespace std; // Function, that return lowest power of 2, bigger than a given number int lowestBiggerPowOf2Than(int number) { int answer; answer = 1 << (int)(log2((double)number - 1) + 1); return answer; } // The structure describing the components from which consists a tree struct Node { int color; long long sumOnSegment; // The default constructor Node() { color = WHITE; sumOnSegment = 0; } // Construct the node by its color and sum on corresponding segment Node(int color, long long sumOnSegment) { this->color = color; this->sumOnSegment = sumOnSegment; } // Define, if this node is painted in some color (some number is assigned) bool isColored() { return color != WHITE; } }; // Function, that pushes information from parent to the children void push(Node *tree, int currentNode, int left, int right) { if (tree[currentNode].isColored()) { int middle = (left + right) / 2; int leftChild = 2 * currentNode; // Pass color from parent to children tree[leftChild].color = tree[currentNode].color; tree[leftChild + 1].color = tree[currentNode].color; // Execute recalculation of the amount in the corresponding segments at children tree[leftChild].sumOnSegment = (long long)(middle - left + 1) * tree[leftChild].color; tree[leftChild + 1].sumOnSegment = (long long)(right - middle) * tree[leftChild + 1].color; // Note parent's node as uncolored tree[currentNode].color = WHITE; } } // Function, that updates the value of all nodes on a segment for the specified void update(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder, int color) { if (leftBorder == left && rightBorder == right) { tree[currentNode] = Node(color, (long long)(right - left + 1) * color); } else { // Executes the delayed update (pushes information) push(tree, currentNode, left, right); int leftChild = 2 * currentNode; int middle = (left + right) / 2; if (rightBorder <= middle) { update(tree, leftChild, left, middle, leftBorder, rightBorder, color); } else if (leftBorder >= middle + 1) { update(tree, leftChild + 1, middle + 1, right, leftBorder, rightBorder, color); } else { update(tree, leftChild, left, middle, leftBorder, middle, color); update(tree, leftChild + 1, middle + 1, right, middle + 1, rightBorder, color); } // Update the amount in corresponding to parent segment tree[currentNode].sumOnSegment = tree[leftChild].sumOnSegment + tree[leftChild + 1].sumOnSegment; } } // Function, that calculates the sum at a specified segment long long sum(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder) { if (left == leftBorder && right == rightBorder) { return tree[currentNode].sumOnSegment; } else { // Executes the delayed update (pushes information) push(tree, currentNode, left, right); int leftChild = 2 * currentNode; int middle = (left + right) / 2; if (rightBorder <= middle) { return sum(tree, leftChild, left, middle, leftBorder, rightBorder); } else if (leftBorder >= middle + 1) { return sum(tree, leftChild + 1, middle + 1, right, leftBorder, rightBorder); } else { return sum(tree, leftChild, left, middle, leftBorder, middle) + sum(tree, leftChild + 1, middle + 1, right, middle + 1, rightBorder); } } } int main() { ios::sync_with_stdio(false); unsigned int quantityOfNumbers; cin >> quantityOfNumbers; unsigned int sizeOfTree = 2 * lowestBiggerPowOf2Than(quantityOfNumbers); Node *tree = new Node[sizeOfTree]; unsigned int quantityOfRequests; cin >> quantityOfRequests; for (unsigned int indexOfRequest = 0; indexOfRequest < quantityOfRequests; indexOfRequest++) { char request; cin >> request; unsigned int leftBorder, rightBorder; if (request == 'A') { int value; cin >> leftBorder >> rightBorder >> value; update(tree, 1, 0, quantityOfNumbers - 1, leftBorder - 1, rightBorder - 1, value); } else if (request == 'Q') { cin >> leftBorder >> rightBorder; cout << sum(tree, 1, 0, quantityOfNumbers - 1, leftBorder - 1, rightBorder - 1) << endl; } } return 0; } |
Links
- Code of the program (supports the query of element by its position and has the timer for analyzing working time)
- Task on e-olymp
- Accepted decision
- Source 1
- Source 2
- Source 3