Segment Tree

st.cpp

#include <iostream>
#include <vector>
using namespace std;

class SegmentTreeNode {
   public:
    int sum = 0;
    int delta = 0;
};

constexpr int leftChild(const int i) { return 2 * i + 1; }

constexpr int rightChild(const int i) { return 2 * i + 2; }

constexpr int midPoint(const int l, const int r) { return (r - l) / 2 + l; }

class SegmentTree {
    vector<SegmentTreeNode> nodes;
    vector<int> data;

    void applyLazy(int index, int left, int right, int leftIndex,
                   int rightIndex) {
        nodes[index].sum += (right - left + 1) * nodes[index].delta;
        if (left != right) {
            nodes[leftIndex].delta += nodes[index].delta;
            nodes[rightIndex].delta += nodes[index].delta;
        }
        nodes[index].delta = 0;
    }

    int queryInTree(int const index, int const left, int const right,
                    int const queryLeft, int const queryRight) {
        if (left > queryRight || right < queryLeft) {
            return 0;
        }

        const int leftIndex = leftChild(index);
        const int rightIndex = rightChild(index);
        const int mid = midPoint(left, right);

        if (nodes[index].delta != 0) {
            applyLazy(index, left, right, leftIndex, rightIndex);
        }

        if (left >= queryLeft && right <= queryRight) {
            return nodes[index].sum;
        }

        if (queryLeft > mid) {
            return queryInTree(rightIndex, mid + 1, right, queryLeft,
                               queryRight);
        } else if (queryRight <= mid) {
            return queryInTree(leftIndex, left, mid, queryLeft, queryRight);
        }

        return queryInTree(leftIndex, left, mid, queryLeft, mid) +
               queryInTree(rightIndex, mid + 1, right, mid + 1, queryRight);
    }

    void modifyInTree(int index, int left, int right, int updateLeft,
                     int updateRight, int delta) {
        const int leftIndex = leftChild(index);
        const int rightIndex = rightChild(index);
        const int mid = midPoint(left, right);

        if (nodes[index].delta != 0) {
            applyLazy(index, left, right, leftIndex, rightIndex);
        }

        if (left > right || left > updateRight || right < updateLeft) {
            return;
        }

        if (left >= updateLeft && right <= updateRight) {
            nodes[index].sum += (right - left + 1) * delta;
            if (left != right) {
                nodes[leftIndex].delta += delta;
                nodes[rightIndex].delta += delta;
            }
            return;
        }

        modifyInTree(leftIndex, left, mid, updateLeft, updateRight, delta);
        modifyInTree(rightIndex, mid + 1, right, updateLeft, updateRight,
                     delta);
        nodes[index].sum = nodes[leftIndex].sum + nodes[rightIndex].sum;
    }

   public:
    SegmentTree(vector<int> const &values)
        : nodes(values.size() * 4), data(values) {
        if (values.size()) {
            Build(0, 0, values.size() - 1);
        }
    }

    void Build(int const index, int const left, int const right) {
        if (left == right) {
            nodes[index].sum = data[left];
            return;
        }

        const int leftIndex = leftChild(index);
        const int rightIndex = rightChild(index);
        const int mid = midPoint(left, right);

        Build(leftIndex, left, mid);
        Build(rightIndex, mid + 1, right);
        nodes[index].sum = nodes[leftIndex].sum + nodes[rightIndex].sum;
    }

    int Query(int const queryLeft, int const queryRight) {
        if (data.size()) {
            return queryInTree(0, 0, data.size() - 1, queryLeft, queryRight);
        }
        return 0;
    }

    void ModifyRange(int updateLeft, int updateRight, int delta) {
        if (data.size()) {
            modifyInTree(0, 0, data.size() - 1, updateLeft, updateRight, delta);
        }
    }
};

void DebugQuery(SegmentTree &st, int queryLeft, int queryRight) {
    cout << "Query(" << queryLeft << ", " << queryRight
         << ") = " << st.Query(queryLeft, queryRight) << endl;
}

int main() {
    SegmentTree st({1, 2, 3, 4, 5, 6});
    DebugQuery(st, 1, 3);
    DebugQuery(st, 2, 5);
    st.ModifyRange(1, 3, 3);
    DebugQuery(st, 1, 3);
    DebugQuery(st, 2, 5);
}