BOJ 백준 10999 : 구간 합 구하기 2

시작하면서

　이번 문제는. 느리게 갱신되는 세그먼트 트리(Segment Tree - Lazy Propagation) 문제이다.

BOJ 10999 - 구간 합 구하기 2

​

문제 이해

​ 해당 문제는 세그먼트 트리를 만들고 나서도 지속적으로 업데이트를 해주어야 한다. 일반적인 세그먼트 트리를 사용해서 매번 요청마다 업데이트를 하는 경우에는 시간초과가 발생하므로 느리게 갱신되는 세그먼트 트리를 사용해야 한다. 다음 링크를 참조하길 바란다.

LINK

​

해결

#include <iostream>
#include <vector>

using namespace std;

/*
    Lazy Propagation Segment Tree
*/
class LPSegmentTree
{
private:
    std::vector<long long> tree;
    std::vector<long long> d;
    int treeSize;
    int treeHeight;

public:
    void Input(int treeSize);
    void BuildInterval(int left, int right);
    void Calculate(int position, int k);
    void Apply(int position, long long value, int k);
    void PushInterval(int left, int right);
    void ModifyInterval(int left, int right, long long value);
    long long QueryInterval(int left, int right);

    void Print();
};

void LPSegmentTree::Input(int treeSize)
{
    this->treeSize = treeSize;
    this->treeHeight = sizeof(int) * 8 - __builtin_clz(treeSize);
    this->tree.resize(this->treeSize * 2);
    this->d.resize(this->treeSize);

    for (int i = 0; i < this->treeSize; i++)
    {
        std::cin >> this->tree[this->treeSize + i];
    }
}

void LPSegmentTree::BuildInterval(int left, int right)
{
    int k = 2;
    for (left += this->treeSize, right += this->treeSize - 1; left > 1; k <<= 1)
    {
        left >>= 1;
        right >>= 1;
        for (int i = right; i >= left; i--)
        {
            Calculate(i, k);
        }
    }
}

void LPSegmentTree::Calculate(int position, int k)
{
    if (this->d[position] == 0)
    {
        this->tree[position] = this->tree[position << 1] + this->tree[position << 1 | 1];
    }
    else
    {
        this->tree[position] += this->d[position] * k;
    }
}

void LPSegmentTree::Apply(int position, long long value, int k)
{
    this->tree[position] += value * k;
    if (position < this->treeSize)
    {
        this->d[position] += value;
    }
}

void LPSegmentTree::PushInterval(int left, int right)
{
    int s = this->treeHeight;
    int k = 1 << (this->treeHeight - 1);
    for (left += this->treeSize, right += this->treeSize - 1; s > 0; s--, k >>= 1)
    {
        for (int i = left >> s; i <= right >> s; i++)
        {
            if (this->d[i] == 0)
                continue;

            Apply(i << 1, this->d[i], k);
            Apply(i << 1 | 1, this->d[i], k);
            this->d[i] = 0;
        }
    }
}

void LPSegmentTree::ModifyInterval(int left, int right, long long value)
{
    if (value == 0)
        return;

    PushInterval(left, left + 1);
    PushInterval(right - 1, right);

    bool cLeft = false, cRight = false;
    int k = 1;
    for (left += this->treeSize, right += this->treeSize; left < right; left >>= 1, right >>= 1, k <<= 1)
    {
        if (cLeft == true)
        {
            Calculate(left - 1, k);
        }

        if (cRight == true)
        {
            Calculate(right, k);
        }

        if (left & 1)
        {
            Apply(left++, value, k);
            cLeft = true;
        }

        if (right & 1)
        {
            Apply(--right, value, k);
            cRight = true;
        }
    }

    for (--left; right > 0; left >>= 1, right >>= 1, k <<= 1)
    {
        if (cLeft == true)
        {
            Calculate(left, k);
        }

        if (cRight == true && (cLeft == false || left != right))
        {
            Calculate(right, k);
        }
    }
}

long long LPSegmentTree::QueryInterval(int left, int right)
{
    PushInterval(left, left + 1);
    PushInterval(right - 1, right);

    long long result = 0;
    for (left += this->treeSize, right += this->treeSize; left < right; left >>= 1, right >>= 1)
    {
        if (left & 1)
        {
            result += this->tree[left++];
        }
        if (right & 1)
        {
            result += this->tree[--right];
        }
    }

    return result;
}

void LPSegmentTree::Print()
{
    for (int i = 1; i < this->tree.size(); i++)
    {
        std::cout << this->tree[i] << " ";
    }
    std::cout << "\n";

    for (int i = 1; i < this->d.size(); i++)
    {
        std::cout << this->d[i] << " ";
    }
    std::cout << "\n";
}

int main()
{
    // sync off
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	// sync off

    LPSegmentTree tree;
    int N, M, K;

    cin >> N >> M >> K;

    tree.Input(N);
    tree.BuildInterval(0, N - 1);

    for (int i = 0; i < M + K; i++)
    {
        int num;

        cin >> num;

        switch (num)
        {
        case 1:
        {
            int left, right;
            long long value;
            cin >> left >> right >> value;
            tree.ModifyInterval(left - 1, right, value);
        }
        break;
        case 2:
        {
            int left, right;
            cin >> left >> right;
            cout << tree.QueryInterval(left - 1, right) << "\n";
        }
        break;
        defualt:
            break;
        }
    }

    return 0;
}