Binary Indexed Tree Range Update

기본적인 BIT(Binary Index Tree : 펜윜트리) 는 빠르게 값을 변경하고, 누적합을 찾을때 사용되는 알고리즘 이다.

하지만, 순차 광역 .. 예를 들어 [a~b] 까지 값을 v 만큼 더해준다... 이런건 어떻게 할까?

이 알고리즘이 바로 Binary Indexed Tree Range Update 임.

 

[참조 : 기타 Index tree 관련 설명은 아래 참조 ]

https://medium.com/@harekrishnamahto18/range-sum-and-update-in-arrays-competitive-programming-82ae5039a16f

 

Range Update에 대한 부분은 아래 상세 내용 참조

https://kartikkukreja.wordpress.com/2013/12/02/range-updates-with-bit-fenwick-tree/

Range updates with BIT / Fenwick Tree

정리하면 다음과 같다.

     1. Point Updates and Range Queries

     2. Range Updates and Point queries

     3. Range Updates and Range Queries

 

1. Point Updates and Range Queries

- 기본 BIT 알고리즘 방식

// long[] FT is the fenwick tree 

// Add v to A[h]
static void update(int h, int v) {
	for (int i = h; i <= MAX_N; i+=(i&-i)) FT[i]+=v;
}

// Return sum A[1...b]
static long sum(int h) {
	long sum = 0;
	for (int i = h; i > 0; i-=(i&-i)) sum+=FT[i];	
	return sum;
}

# Return sum A[a...b]
static long sum(int a, int b) {
	return sum(b, FT) - query(a-1, FT);
}

Given an array A of N numbers, we need to support adding a value v to any element A[p] and querying the sum of numbers A[a] + A[a+1] + … + A[b], both operations in O(log N). Let ft[N+1] denotes the underlying fenwick tree.

 

2. Range Updates and Point queries

- Range Update를 진행하고, 해당 배열지점의 값을 찾는 알고리즘

// A[] is the original array
// long[] FT is the fenwick tree maintaining the diffs initialized with 0

// Add v to A[h]
static void update(int h, int v) {
	for (int i = h; i <= MAX_N; i+=(i&-i)) FT[i]+=v;
}

// Add v to A[a...b] 
static void update(int a, int b, int v) {
	update(a, v);
    update(b+1, -v);
}

// Return A[h]
static long query(int h) {
	long sum = 0;
    for (int i = h; i > 0; i-=(i&-i)) sum+=FT[i];
    return sum + A[h];
}

Given an array A of N numbers, we need to support adding a value v to each element A[a…b] and querying the value of A[p], both operations in O(log N). Let ft[N+1] denote the underlying fenwick tree

 

3. Range Updates and Range Queries

- Range Update 를 진행하고, Range 합을 구하는 알고리즘

// A[] is the original array
// long[] FT is the fenwick tree maintaining the diffs initialized with 0
// using two BITs B1[N+1], B2[N+1].

// Add v to A[h]
static void update(int h, int v, long[] FT) {
	for (int i = h; i <= MAX_N; i+=(i&-i)) FT[i]+=v;
}

// Add v to A[a...b]
static void update(int a, int b, int v, long[] FT) {
	update(a, v, B1);
    update(b+1, -v, B1);
    update(a, v*(a-1), B2);
    update(b+1, -v * b, B2);
}

static long query(int h, long[] FT) {
	long sum = 0;
    for (int i = h; i > 0; i-=(i&-i)) sum+=FT[i];
    return sum;
}

// Return sum A[1...b]
static long query(int h) {
	return query(h, B1) * h  - query(h, B2);
}

//Return sum A[a...b]
static long query(int a, int b) {
	return query(b) - query(a-1);
}

Given an array A of N numbers, we need to support adding a value v to each element A[a…b] and querying the sum of numbers A[a…b], both operations in O(log N). This can be done by using two BITs B1[N+1], B2[N+1].

 

Range update의 구간 합을 구하는 방법은 어렵다..ㅠㅠ

 

---