遅延セグ木との和解

ついにセグメントツリーの遅延評価を学習しました。

CHIEN Segment Treeとは

遅延セグ木は呼びやすいから勝手にそう呼んでるだけです。
みんな大好きなセグメント木を、区間内に一様に足すようなクエリに対応させたい。
そんな思いから生まれたテクニックです。

区間に一様に足すだけでなく、色々な応用があるらしいです。
詳しい解説はkyuridenamidaさんの記事を見てください。

コード

POJ3468の「A Simple Problem with Integers」を解けるコードです。
http://poj.org/problem?id=3468

• 区間に一様に値を足す
• 区間の総和を求める

の2つのクエリに応えます。

using namespace std;

#define int long long

const int MAX_N = 1<<17;

struct Node
{
    int sum, laziness;
};

int N, Q, A[MAX_N];
int segSize;
Node node[MAX_N*2 - 1];

void InitSize()
{
    segSize = 1;
    while (segSize < N) segSize *= 2;
}

void InitNode()
{
    for (int i = 0; i < N; i++)
    {
        node[segSize - 1 + i].sum = A[i];
    }
    if (segSize == 1) return;
    for (int i = segSize - 2; i >= 0; i--)
    {
        node[i].sum = node[i*2 + 1].sum + node[i*2 + 2].sum;
    }
}

inline void UpdateLaziness(int length, int k)
{
    node[k*2 + 1].laziness += node[k].laziness;
    node[k*2 + 2].laziness += node[k].laziness;
    node[k].sum += node[k].laziness*length;
    node[k].laziness = 0;
}

int Add(int l, int r, int k, int a, int b, int v)
{
    if (r <= a || b <= l) return node[k].sum + node[k].laziness*(r - l);
    if (a <= l && r <= b) return node[k].sum + (node[k].laziness += v)*(r - l);
    UpdateLaziness(r - l, k);
    int mid = (l + r)/2;
    return node[k].sum = Add(l, mid, k*2 + 1, a, b, v) + Add(mid, r, k*2 + 2, a, b, v);
}

int GetSum(int l, int r, int k, int a, int b)
{
    if (r <= a || b <= l) return 0;
    if (a <= l && r <= b) return node[k].sum + node[k].laziness*(r - l);
    UpdateLaziness(r - l, k);
    int mid = (l + r)/2;
    return GetSum(l, mid, k*2 + 1, a, b) + GetSum(mid, r, k*2 + 2, a, b);
}

signed main()
{
    cin >> N >> Q;
    InitSize();
    for (int i = 0; i < N; i++)
    {
        scanf("%lld", A + i);
    }
    InitNode();
    for (int i = 0; i < Q; i++)
    {
        char type;
        int a, b;
        scanf(" %c%lld%lld", &type, &a, &b);
        if (type == 'C')
        {
            int c;
            scanf("%lld", &c);
            Add(0, segSize, 0, a - 1, b, c);
        }
        else printf("%lld\n", GetSum(0, segSize, 0, a - 1, b));

    }
    return 0;
}

UpdateLaziness()の node[k].sum += ... の部分、Add()から呼び出すときには必要ない(どうせ子ノードから求めるから)のですが、あっても困らないので無視してます。