블록 분할 기법

길이가 n인 배열을 약 √n개의 블록으로 나누면, 각 블록의 크기는 최대 √n이 되며, 임의의 구간 연산은 최대 √n개의 완전한 블록과 두 개의 부분 블록으로 표현 가능하다.

시간 복잡도는 기존의 O(n²)에서 O(n√n)으로 개선된다.

기본 구현 틀

#include <iostream>
#include <cmath>
#include <cstdio>

using namespace std;

typedef long long LL;
const int MAX_N = 100010;
const int BLOCK_SIZE = 350;

int n, q;
int block_count;
LL block_add[BLOCK_SIZE], block_sum[BLOCK_SIZE];
int arr[MAX_N];

// 블록 인덱스 반환
int get_block(int pos) {
    return pos / block_count;
}

// 범위에 값을 추가하는 함수
void update_range(int left, int right, int delta) {
    if (get_block(left) == get_block(right)) {
        // 같은 블록 내에서는 직접 처리
        for (int i = left; i <= right; ++i) {
            arr[i] += delta;
            block_sum[get_block(i)] += delta;
        }
    } else {
        int i = left, j = right;
        // 양 끝 블록 처리
        while (get_block(i) == get_block(left)) {
            arr[i] += delta;
            block_sum[get_block(i)] += delta;
            ++i;
        }
        while (get_block(j) == get_block(right)) {
            arr[j] += delta;
            block_sum[get_block(j)] += delta;
            --j;
        }
        // 중간 블록들에 일괄 업데이트
        for (int k = get_block(i); k <= get_block(j); ++k) {
            block_sum[k] += block_count * delta;
            block_add[k] += delta;
        }
    }
}

// 범위의 합 계산
LL query_sum(int left, int right) {
    LL result = 0;
    if (get_block(left) == get_block(right)) {
        for (int i = left; i <= right; ++i)
            result += arr[i] + block_add[get_block(i)];
    } else {
        int i = left, j = right;
        while (get_block(i) == get_block(left))
            result += arr[i] + block_add[get_block(i)], ++i;
        while (get_block(j) == get_block(right))
            result += arr[j] + block_add[get_block(j)], --j;
        for (int k = get_block(i); k <= get_block(j); ++k)
            result += block_sum[k];
    }
    return result;
}

int main() {
    scanf("%d%d", &n, &q);
    block_count = static_cast<int>(sqrt(n));

    for (int i = 1; i <= n; ++i) {
        scanf("%d", &arr[i]);
        block_sum[get_block(i)] += arr[i];
    }

    char op[2];
    int l, r, d;
    while (q--) {
        scanf("%s%d%d", op, &l, &r);
        if (*op == 'C') {
            scanf("%d", &d);
            update_range(l, r, d);
        } else {
            printf("%lld\n", query_sum(l, r));
        }
    }

    return 0;
}

블록 기반 연결 리스트

각 블록에 전후 링크를 포함하여 연결 리스트처럼 관리한다. 삽입/삭제 시에도 효율적인 구조 유지가 가능하다. 그러나 시간 복잡도를 보장하기 위해 정기적으로 merge 연산을 수행하여 작은 블록들을 통합해야 한다.

문제 예시: [NOI2003] 텍스트 편집기

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int MAX_NODES = 2010;
const int MAX_CHARS = 2000;

struct BlockNode {
    char data[MAX_CHARS + 1];
    int size, prev, next;
} nodes[MAX_NODES];

char input_buffer[2000010];
int free_list[MAX_NODES], free_top;
int cursor_node, cursor_pos;

// 커서 위치 이동
void move_cursor(int pos) {
    cursor_node = 0;
    cursor_pos = 0;
    while (pos > nodes[cursor_node].size) {
        pos -= nodes[cursor_node].size;
        cursor_node = nodes[cursor_node].next;
    }
    cursor_pos = pos - 1;
}

// 새 블록 삽입 (기존 노드 오른쪽)
void insert_after(int target, int new_idx) {
    nodes[new_idx].next = nodes[target].next;
    nodes[nodes[target].next].prev = new_idx;
    nodes[target].next = new_idx;
    nodes[new_idx].prev = target;
}

// 블록 삭제 및 메모리 재활용
void remove_node(int idx) {
    nodes[nodes[idx].prev].next = nodes[idx].next;
    nodes[nodes[idx].next].prev = nodes[idx].prev;
    nodes[idx].prev = nodes[idx].next = nodes[idx].size = 0;
    free_list[++free_top] = idx;
}

// 커서 뒤에 문자 삽입
void insert_text(int count) {
    if (cursor_pos < nodes[cursor_node].size - 1) {
        int split_node = free_list[free_top--];
        int src_start = cursor_pos + 1;
        for (int i = src_start; i < nodes[cursor_node].size; ++i)
            nodes[split_node].data[nodes[split_node].size++] = nodes[cursor_node].data[i];
        nodes[cursor_node].size = cursor_pos + 1;
        insert_after(cursor_node, split_node);
    }

    int current = cursor_node;
    for (int i = 0; i < count;) {
        int new_node = free_list[free_top--];
        while (nodes[new_node].size < MAX_CHARS && i < count)
            nodes[new_node].data[nodes[new_node].size++] = input_buffer[i++];
        insert_after(current, new_node);
        current = new_node;
    }
}

// 커서 뒤의 문자 삭제
void delete_text(int count) {
    if (nodes[cursor_node].size - 1 - cursor_pos >= count) {
        for (int i = cursor_pos + count + 1, j = cursor_pos + 1; i < nodes[cursor_node].size; ++i, ++j)
            nodes[cursor_node].data[j] = nodes[cursor_node].data[i];
        nodes[cursor_node].size -= count;
    } else {
        count -= nodes[cursor_node].size - cursor_pos - 1;
        nodes[cursor_node].size = cursor_pos + 1;
        while (nodes[cursor_node].next && count >= nodes[nodes[cursor_node].next].size) {
            int del_node = nodes[cursor_node].next;
            count -= nodes[del_node].size;
            remove_node(del_node);
        }
        int tail_node = nodes[cursor_node].next;
        for (int i = 0, j = count; j < nodes[tail_node].size; ++i, ++j)
            nodes[tail_node].data[i] = nodes[tail_node].data[j];
        nodes[tail_node].size -= count;
    }
}

// 커서부터 특정 수의 문자 출력
void output_chars(int count) {
    if (nodes[cursor_node].size - 1 - cursor_pos >= count) {
        for (int i = cursor_pos + 1, j = 0; j < count; ++i, ++j)
            putchar(nodes[cursor_node].data[i]);
    } else {
        for (int i = cursor_pos + 1; i < nodes[cursor_node].size; ++i)
            putchar(nodes[cursor_node].data[i]);
        count -= nodes[cursor_node].size - cursor_pos - 1;
        int cur = cursor_node;
        while (nodes[cur].next && count >= nodes[nodes[cur].next].size) {
            int node = nodes[cur].next;
            for (int i = 0; i < nodes[node].size; ++i)
                putchar(nodes[node].data[i]);
            count -= nodes[node].size;
            cur = node;
        }
        int last = nodes[cur].next;
        for (int i = 0; i < count; ++i)
            putchar(nodes[last].data[i]);
    }
    puts("");
}

// 커서 이동: 왼쪽
void move_left() {
    if (cursor_pos == 0) {
        cursor_node = nodes[cursor_node].prev;
        cursor_pos = nodes[cursor_node].size - 1;
    } else {
        --cursor_pos;
    }
}

// 커서 이동: 오른쪽
void move_right() {
    if (cursor_pos < nodes[cursor_node].size - 1) {
        ++cursor_pos;
    } else {
        cursor_node = nodes[cursor_node].next;
        cursor_pos = 0;
    }
}

// 인접한 작고 비어 있지 않은 블록 통합
void merge_blocks() {
    for (int i = nodes[0].next; i != 0; i = nodes[i].next) {
        while (nodes[i].next && nodes[i].size + nodes[nodes[i].next].size < MAX_CHARS) {
            int right_node = nodes[i].next;
            for (int j = nodes[i].size, k = 0; k < nodes[right_node].size; ++j, ++k)
                nodes[i].data[j] = nodes[right_node].data[k];
            if (cursor_node == right_node) {
                cursor_node = i;
                cursor_pos += nodes[i].size;
            }
            nodes[i].size += nodes[right_node].size;
            remove_node(right_node);
        }
    }
}

int main() {
    for (int i = 1; i < MAX_NODES; ++i)
        free_list[++free_top] = i;

    int operations;
    scanf("%d", &operations);

    // 초기 빈 노드 삽입
    nodes[0].next = free_list[free_top--];
    nodes[0].size = 1;
    nodes[0].data[0] = '>';
    nodes[nodes[0].next].prev = 0;
    cursor_node = 0;
    cursor_pos = 0;

    char command[10];
    while (operations--) {
        scanf("%s", command);
        if (strcmp(command, "Move") == 0) {
            int pos;
            scanf("%d", &pos);
            move_cursor(pos + 1);
        } else if (strcmp(command, "Insert") == 0) {
            int cnt;
            scanf("%d", &cnt);
            int idx = 0;
            while (cnt--) {
                input_buffer[idx] = getchar();
                if (input_buffer[idx] >= 32 && input_buffer[idx] <= 126)
                    ++idx, --cnt;
            }
            insert_text(idx);
            merge_blocks();
        } else if (strcmp(command, "Delete") == 0) {
            int cnt;
            scanf("%d", &cnt);
            delete_text(cnt);
            merge_blocks();
        } else if (strcmp(command, "Get") == 0) {
            int cnt;
            scanf("%d", &cnt);
            output_chars(cnt);
        } else if (strcmp(command, "Prev") == 0) {
            move_left();
        } else {
            move_right();
        }
    }

    return 0;
}

이러한 구조는 특히 부분 점수 문제에서 유용하며, 논리적 접근이 간단하고 코드 수정이 쉬운 장점이 있다.