Sqrt Decomposition (평방분할)

코드

#include <stdio.h>
#include <math.h>
#include <algorithm>

using namespace std;

typedef long long int lld;

int ar[100003];
lld sq[1000];
int sz, n;

void init() {
    int i;
    sz = sqrt(n);
    for (i = 1; i <= n; i++)
        sq[i / sz] += ar[i];
}

void update(int pos, lld val) {
    lld diff = val - ar[pos];
    ar[pos] = val;
    sq[pos / sz] += diff;
}

lld query(int lo, int hi) {
    lld ret = 0;

    if (lo == 1 && hi == 2)
        hi = hi;
    while (lo <= hi && lo % sz > 0)
        ret += ar[lo++];
    while (lo <= hi && (hi + 1) % sz > 0)
        ret += ar[hi--];
    while (lo <= hi) {
        ret += sq[lo / sz];
        lo += sz;
    }

    return ret;
}

int main()
{
    int q, i, x, y, a, b;

    scanf("%d%d", &n, &q);
    for (i = 1; i <= n; i++)
        scanf("%d", &ar[i]);
    init();
    while (q--) {
        scanf("%d%d%d%d", &x, &y, &a, &b);
        printf("%lld\n", query(min(x, y), max(x, y)));
        update(a, b);
    }
    return 0;
}

https://www.acmicpc.net/problem/1275 문제에 대한 풀이

정리

• N 개의 배열에 대해 update (ar[pos] = val) 또는 query (lo~hi 에 대한 합, 최대, 최소 등) 을 수행해야 할 때,
• 배열을 sqrt(n) 개로 나누어 update 를 수행하면 O(1), query 를 수행하면 (sqrt(n)) 의 성능을 얻을 수 있다.
  • update 의 경우 배열의 원소, sqrt 로 나누어진 배열을 업데이트 하면 끝난다
  • query 의 경우 최대 sqrt(n) 개에 대한 대표 값 + 앞 뒤로 각 원소를 탐색해야 하지만 크기가 sqrt(n) 을 넘지 않는다
    • 따라서 시간복잡도는 sqrt(n) 이 된다

관련문제

https://www.acmicpc.net/workbook/view/346

참고

https://kesakiyo.tistory.com/22