세그먼트 트리와 바이너리 인덱스 트리 (템플릿)
세그먼트 트리 1 - 구간 연산 및 합계
이 템플릿은 구간 더하기 연산과 구간 합을 구하는 세그먼트 트리를 구현합니다.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef long long ll;
int arrSize, queryCount;
const int MAX ...
7월 28일 18:20에 게시됨
펜윅 트리를 활용한 역쌍 계산 알고리즘
역쌍(Inversion Pair)이란 주어진 양의 정수 배열에서 인덱스 i가 j보다 작으면서 값은 a[i]가 a[j]보다 큰 경우, 즉 i < j && a[i] > a[j]를 만족하는有序对(순서쌍)를 의미한다.
这类 문제를 풀 때 가장 먼저 떠올리는 방법은 병합 정렬을 이용하는 것이다. 그러나 今回は 펜윅 트리(Fenwick Tree) 또는 BIT(Binary Indexed Tree)라는 자료구조를 활용하여 ...
7월 25일 03:34에 게시됨
바이너리 인덱스 트리: 구현과 활용
바이너리 인덱스 트리
1. 점 업데이트와 구간 합 查询
lowbit 함수
바이너리 인덱스 트리의 핵심은 lowbit 연산입니다:
lowbit(x) = x & (-x)
이 연산은 x의 이진 표현에서 가장 오른쪽에 있는 1의 위치 값을 반환합니다.
예를 들어, x = (0010010011000)₂ 라면:
-x = ~x + 1 = (1101101101000)₂
x & (-x) = (0000000001000)₂
동작 원리
배열 a[1...n]이 ...
7월 10일 04:24에 게시됨