트리 배열을 활용한 효율적인 구간 합 계산
트리 배열(Fenwick Tree 또는 Binary Indexed Tree, BIT)는 동적 배열에서 구간 합과 단일 요소 갱신을 매우 효율적으로 처리할 수 있도록 설계된 자료구조입니다. 이 구조는 O(log n) 시간 내에 전위 합(prefix sum)을 계산하고, 특정 위치의 값을 수정할 수 있어 빈번한 갱신과 질의가 필요한 문제에서 큰 성능 이점을 제공합니다.
기본 원리
트리 배열은 ...
7월 22일 06:38에 게시됨
동적 역순 쌍 계산 문제
문제 개요
길이가 \(n\)인 순열 \(a\)가 주어진다. 두 원소를 교환할 때마다 역순 쌍의 개수를 2로 나눈 나머지를 출력해야 한다.
입력 형식
첫 번째 줄에는 양의 정수 \(n\)이 주어진다.
두 번째 줄에는 순열 \(a\)를 구성하는 \(n\)개의 숫자가 주어진다.
세 번째 줄에는 질의 수 \(q\)가 주어진다.
다음 \(q\)줄에는 각각 두 개의 양의 정수가 주어지며, 이는 \(a_i\)와 ...
6월 11일 16:49에 게시됨
BIT(페니크 트리) 개념 정리 및 문제 풀이
BIT(페니크 트리) 개요
BIT(Binary Indexed Tree)는 구간 합을 빠르게 계산하고, 특정 인덱스의 값을 업데이트할 수 있는 자료구조입니다.
lowbit 연산을 기반으로 하여 시간 복잡도 O(log N)을 보장합니다.
P3374: 기본적인 BIT 연산
단일 값 갱신과 구간 합을 처리하는 가장 기초적인 템플릿 문제입니다.
#include <bits/stdc++.h>
using namespace std;
int n ...
5월 26일 07:58에 게시됨