10999번: 구간 합 구하기 2

https://www.acmicpc.net/problem/10999


$O(n+(m+k)\lg n)$

lazy propagation, bit 같이 방법은 많은데 세그먼트 트리에서 변수 두개를 이용하여 해결하는 방법에 대해서만 쓰겠다.
세그먼트 트리를 이용할 때 변수 하나만으로는 문제를 해결하기 어렵다고 느낄 것이다.
변수를 하나만 사용할 경우, 구간 갱신시에 찾는 구간에 해당하는 노드들에 합을 누적시킨다해도 구간 쿼리 처리시 범위에 따라 이전에 저장한 값에 접근하지 못할 수 있다.
이런 문제점을 해결하기 위해 변수를 두 개 사용하여 하나는 자식들을 탐색하지 않고도 해당 노드의 구간에 해당하는 값에 접근할 수 있도록 하고, 다른 하나는 루트로 부터 내려올때마다 어떠한 값을 저장시켜 해당 구간의 부분 구간에 저장될 값들을 접근할 수 있도록 해야한다.
이러한 점을 고려하여 각 노드는 구간의 전체 합, 구간의 각 위치에 동일하게 더해야 하는 값을 저장하는 두 가지의 변수를 가지게 한다. 이를 각각 t1,t2라 하자.
업데이트시
만족하는 구간을 찾으면 그 노드의 t2에 d를 누적한다.
루트로부터 만족하는 구간을 찾을 때까지 거쳐오는 노드들의 각 t1에 자신의 구간 중 찾는 구간에 더해질 값들을 누적한다.
쿼리처리시
만족하는 구간을 찾으면 그 노드의 t1값을 누적한다.
루트로부터 만족하는 구간을 찾을 때까지 거쳐오는 노드들마다 t2*(자신의 구간 중 찾는 구간 크기)를 누적한다.

#include<stdio.h>
#include<algorithm>
using namespace std;
const int MAX_N = 1e6;
typedef long long ll;
int n, m, k;
ll t1[MAX_N * 4], t2[MAX_N * 4];
void update(int h, int l, int r, int gl, int gr, ll x) {
    if (r < gl || gr < l) return;
    t1[h] += (min(r, gr) - max(l, gl) + 1)*x;
    if (gl <= l && r <= gr) {
        t2[h] += x;
        return;
    }
    update(h * 2 + 1, l, (l + r) / 2, gl, gr, x);
    update(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr, x);
}
ll query(int h, int l, int r, int gl, int gr) {
    if (r < gl || gr < l) return 0;
    if (gl <= l && r <= gr) return t1[h];
    return query(h * 2 + 1, l, (l + r) / 2, gl, gr)
        + query(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr)
        + (min(r, gr) - max(l, gl) + 1)*t2[h];
}
int main() {
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 1, x; i <= n; i++) scanf("%d", &x), update(0, 1, n, i, i, x);
    ll w;
    for (int i = 0, x, y, z; i < m + k; i++) {
        scanf("%d", &x);
        if (x == 1) {
            scanf("%d %d %lld", &y, &z, &w);
            update(0, 1, n, y, z, w);
        }
        else {
            scanf("%d %d", &y, &z);
            printf("%lld\n", query(0, 1, n, y, z));
        }
    }
    return 0;
}