We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Arrays
  4. Array Manipulation
  5. Discussions

Array Manipulation

  • aszubarev
     + 0 comments

    I implemented the solution using a segment tree!

    It wouldn't be easy. I had to improve the familiar segment tree. I want to talk about all the improvements in order. Here is my solution.

    #include <iostream>
#include <fstream>
#include <vector>

using namespace std;


class SegmentTreeNode {

public:

    int left;
    int right;
    bool is_leaf;
    long value;
    long operation;
    SegmentTreeNode *left_child;
    SegmentTreeNode *right_child;

    SegmentTreeNode(int left, int right) {
        this->left = left;
        this->right = right;
        this->is_leaf = bool(right - left == 1);
        this->value = 0;
        this->operation = 0;
        this->left_child = nullptr;
        this->right_child = nullptr;
    }

    ~SegmentTreeNode() {
        delete this->left_child;
        delete this->right_child;
    }

    SegmentTreeNode *getLeftChild() {
        if (!this->is_leaf && this->left_child == nullptr) {
            int mid = (this->right - this->left) / 2;
            this->left_child = new SegmentTreeNode(
                    this->left,
                    this->left + mid
            );
        }
        return this->left_child;
    }

    SegmentTreeNode *getRightChild() {
        if (!this->is_leaf && this->right_child == nullptr) {
            int mid = (this->right - this->left) / 2;
            this->right_child = new SegmentTreeNode(
                    this->left + mid,
                    this->right
            );
        }
        return this->right_child;
    }

    static void propagate(SegmentTreeNode *node) {
        if (node->getLeftChild() != nullptr) {
            SegmentTreeNode::operationNode(
                    node->getLeftChild(),
                    node->operation
            );
        }
        if (node->getRightChild() != nullptr) {
            SegmentTreeNode::operationNode(
                    node->getRightChild(),
                    node->operation
            );
        }
        node->operation = 0;
    }

    static long getResult(  // NOLINT(misc-no-recursion)
            SegmentTreeNode *node,
            int left,
            int right
    ) {
        SegmentTreeNode::propagate(node);
        if (left <= node->left && node->right <= right) {
            return node->value;
        }
        long result = 0;
        if (left < node->getLeftChild()->right) {
            result = SegmentTreeNode::operationResult(
                    result,
                    SegmentTreeNode::getResult(
                            node->getLeftChild(),
                            left,
                            right
                    )
            );
        }
        if (node->getRightChild()->left < right) {
            result = SegmentTreeNode::operationResult(
                    result,
                    SegmentTreeNode::getResult(
                            node->getRightChild(),
                            left,
                            right
                    )
            );
        }

        return result;
    }

    static void update( // NOLINT(misc-no-recursion)
            SegmentTreeNode *node,
            int left,
            int right,
            long value
    ) {
        SegmentTreeNode::propagate(node);
        if (left <= node->left && node->right <= right) {
            return SegmentTreeNode::operationNode(node, value);
        }

        if (left < node->getLeftChild()->right) {
            SegmentTreeNode::update(
                    node->getLeftChild(),
                    left,
                    right,
                    value
            );
        }
        if (node->getRightChild()->left < right) {
            SegmentTreeNode::update(
                    node->getRightChild(),
                    left,
                    right,
                    value
            );
        }

        node->value = SegmentTreeNode::operationResult(
                node->getLeftChild()->value,
                node->getRightChild()->value
        );

    }

    static long operationResult(
            long left_operand,
            long right_operand
    ) {
        return std::max(left_operand, right_operand);
    }

    static void operationNode(SegmentTreeNode *node, long value) {
        node->value += value;
        node->operation += value;
    }
};

long arrayManipulation(int n, vector<vector<int>> &queries) {
    auto *tree = new SegmentTreeNode(0, n);

    for (vector<int> query: queries) {
        int a, b, k;
        a = query[0] - 1;
        b = query[1];
        k = query[2];
        SegmentTreeNode::update(tree, a, b, k);
    }

    long result = SegmentTreeNode::getResult(tree, 0, n);
    delete tree;
    return result;
}

    Schematically, the structure looks like this.

    Example for left, right = 0, 4
   {0, 1, 2, 3}                     [0, 4)
  {0, 1}  {2, 3}                 [0, 2) [2, 4)
 {0} {1}  {2} {3}         [0, 1) [1, 2) [2, 3) [3, 4)

    First improvement - lazy propagation.

    There is no need to apply the operation to child elements if the target range overlaps the found element's range. So I update the found element and mark it. And if it is necessary to access child elements, the operation of the parent will propagate down.

    Second improvement - lazy instantiation of child elements

    There is no need to immediately instantiate the entire tree. Some of its nodes may not even be required in special test cases. Otherwise it would take extra time.

    Some math

    This tree is implemented in such a way that it can be used to solve different tasks by overriding only two methods operationResult and operationNode.

    operationNode - the operation to be performed on the node. It can be an addition operation to the current value, an assignment operation, a multiplication operation, and so on. One requirement - the operation must be associative. Operation sum is associative.

    operationResult - an operation to get a result on a segment. It can be sum, maximum, minimum, etc. In our problem, this is the operation max. This requirement is obtained due to the peculiarity of the implementation of the tree - lazy propagation.

    The cumulative main requirement for these two methods is that they must be distributive. Note that I have written methods, not operations. There is a classic problem for a tree of segments - to increase the value on the segment and get the sum on the segment. The increase operation and the sum operation are not distributive. See for yourself. Incrementing the parent by 3 is not the same as incrementing each child by 3.

         {3}+3
{1}+3    {2}+3

(1 + 2) + 3 != (1 + 3) + (2 + 3)


(1 + 2) - child elements with value 1 and 2
3 - the value by which each element should be incremented

    For this task, it is necessary to make the methods distributive. This is possible if the length of the segment is taken into account. Like this.

        static long operationResult(
            long left_operand,
            long right_operand
    ) {
        return left_operand + right_operand;
    }

    static void operationNode(SegmentTreeNode *node, long value) {
        node->value += value * (node -> right - node -> left);
        node->operation += value;
    }

    Methods are now distributive

         {3}+3+3
{1}+3    {2}+3

(1 + 2) + (3 * 2)  == (1 + 3 * 1) + (2 + 3 * 1)

(1 + 2) - child elements with value 1 and 2
3 - the value by which each element should be incremented
* 2 - the length of the segment of the parent element
* 1 - the length of the segment of the child element

    If these requirements are taken into account, then any problem that satisfies them can be solved.

    P.S. I first solved this problem in python. But this solution worked out in 15 seconds on large test cases. It wasn't enough. Rewriting the solution in C++, the result was obtained in less than a second. According to my calculations, the complexity of this solution is O(M log(N)).

    Happy codding!