“This is the third day of my participation in the November Gwen Challenge. See details of the event: The last Gwen Challenge 2021”.

define

The so-called tree array, the logical structure is a tree, but using the array implementation, he can solve the problem of single point modification interval query class, belongs to a prefix sum optimization.

lowbit

The lowbitlowbitlowbit is the weight of 111, the lowest binary number, For example, the binary number 110011001100 lowbit is the binary number 100100100, so the weight is 22=42^2=422=4, Lowbit (x)lowbit(x)lowbit(x) In fact, lowbit (x) = x & lowbit (- x) (x) = x \ & (-) x lowbit (x) = x & (- x), & \ && said bitwise and operation.

inline int lowbit(int i){returni&(-i); }Copy the code

Tree array structure

From above,orangebirdIn the figure
A i A_i Represents the original array,
C i C_i said
A i A_i Corresponding tree array.

CiC_iCi maintains AiA_iAi interval information, so what interval does CiC_iCi maintain? Lowbit (I)lowbit(I)

lowbit(1)=1 lowbit(2)=2 lowbit(3)=1 lowbit(4)=1 lowbit(5)=1 lowbit(6)=2 lowbit(7)=1 lowbit(8)=8

As can be seen, the maintenance length of CiC_iCi is lowbit(I)lowbit(I)lowbit(I)lowbit(I). The maintenance interval is [I − Lowbit (I)+1, I][I -lowbit(I)+1, I][I − Lowbit (I)+1, I].

As C3C3C3 maintenance interval is [2 – lowbit (2) + 1, 2], [2 – lowbit (2) + 1, 2], [2 – lowbit (2) + 1, 2] is [1, 2] [1, 2] [1, 2]. C8C8C8 maintenance interval is [8 – lowbit (8) + 1, 8] [8 – lowbit (8) + 1, 8] [8 – lowbit (8) + 1, 8] or [1] [1] [1].

So what bit values might be affected by the CiC_iCi of the tree array? C1C1C1, for example, 1 + lowbit (1) = 2, 2 + lowbit (2) = 4, 4 + lowbit (4) = 81 + lowbit (1) = 2, 2 + lowbit (2) = 4, 4 + lowbit (4) = 81 + lowbit (1) = 2, 2+lowbit(2)=4, 4+ Lowbit (4)=8, we find that the third value recursively affects all the parent nodes, and the parent node numbered iii in the tree array is numbered as I +lowbit(I) I +lowbit(I) I +lowbit(I) I.

Application, for example,

Single point of change range and query

Considering a class of problems, given continuous intervals of length Lenlenlen and initial values for each endpoint, a single point modification is now allowed during a query, where each query is the sum of the intervals [L,r][L,r][L, R].

We can transform a tree-like array with contiguous intervals of [1,len][1,len][1,len], assuming that AAA is the original array and CiC_iCi is the tree-like array maintained, maintaining intervals and information.

Update function

  • Since tree array initialization needs to borrow the update function, we put it first. What is done is to add XXX to both number III and the number positions affected by iii, and a decrease can be thought of as adding − X-x − X.
void update(int i,int x){
	while(i<=len){
		C[i]+=x;/ / plus x
		i+=lowbit(i);// Next affected I}}Copy the code

Initialization function

void init(a){
	memset(C,0.sizeof(C));// Initialize the C array to 0
	for(int i=1; i<=len; i++){update(i,A[i]);// insert A[I] recursively}}Copy the code

Prefixes and queries

  • Due to the dendritic array is maintenance interval [I – lowbit (I) + 1, I] [I – lowbit (I) + 1, I] [I – lowbit (I) + 1, I], we can’t directly obtained [l, r] [l, r] [l, r] and, so we first [I] 1, [1] I [, I] and, Remember to Sum (I) the Sum (I) the Sum (I), the Sum] [l, r = Sum (r) – the Sum (l – 1) Sum_ {} [l, r] = Sum (r) – the Sum (l – 1) Sum] [l, r = Sum (r) – the Sum (l – 1).
int Sum(int i){// Calculate the sum of [1, I
	int sum=0;
	while(i){
		sum+=C[i};// Within the interval
		i-=lowbit(i);// Last unaffected number
	}
	return sum;
}
Copy the code

Range queries

  • According to the difference of ideas, can be obtained by [l, r] [l, r] [l, r] and, namely the Sum] [l, r = Sum (r) – the Sum (l – 1) Sum_ {} [l, r] = Sum (r) – the Sum (l – 1) Sum] [l, r = Sum (r) – the Sum (l – 1).
int query(int l,int r){
	return Sum(r)-Sum(l- 1);
}
Copy the code

Range change single point query

Consider a class of problems, given a continuous interval of length lenlenlen and the initial value of each endpoint, now allow to increase or decrease some interval during the query, each time asking for the value of point III.

We can convert a tree-like array with a continuous interval of [1,len][1,len][1,len], assuming that AAA is the original array and CiC_iCi is the maintained tree-like array.

This problem requires the use of the difference array BiB_iBi, which records Ai−Ai−1A_i-A_{i-1}Ai−Ai−1. ∑ I =1nBi=An\sum_{I =1}^{n} B_i=A_n∑ I =1nBi=An. CiC_iCi the maintenance BiB_iBi interval [l, r] [l, r] [l, r] and, therefore nci ∑ I = 1 = An \ sum_ {I = 1} ^ {n} C_i = A_n ∑ nci = An I = 1.

When the interval [L,r][L,r][L,r] increases XXX, ClC_lCl increases XXX, indicating that both Al ~ ArA_l\ SIM A_rAl ~ Ar increase XXX. However, the corresponding Ar+1 ~ AlenA_{r+1}\sim A_{len}Ar+1 ~ Alen is also affected, so Cr+1C_{r+1}Cr+1 needs to be reduced by XXX to ensure that the following ranges are not affected.

Update function

void update(int i,int x){
	while(i<=len){
		C[i]+=x;/ / plus x
		i+=lowbit(i);// Next affected I}}Copy the code

Initialization function

void init(a){
	memset(C,0.sizeof(C));// Initialize the C array to 0
	for(int i=1; i<=len; i++){update(i,A[i]-A[i- 1]);// insert B[I]=A[I] -a [I -1], note that A[0]=0}}Copy the code

Interval changes

void change(int l,int r,int x){
	update(l,x);
	update(r+1,-x);
}
Copy the code

A single point of query

int query(int i){
	int sum=0;
	while(i){
		sum+=C[i];
		i-=lowbit(i);
	}
	return sum;
}
Copy the code

Interval maximum value problem

Considering a class of problems, the continuous interval of length lenlenlen is given, and the initial value of each endpoint is given. Now a single point of modification is allowed during the query. Each query is the maximum or minimum information of the interval [L,r][L,r][L, R].

We can convert the tree-like array whose continuous interval is [1,len][1,len][1,len], assuming that AAA is the original array and CiC_iCi is the maintained tree-like array, Record is [I – lowbit (I) + 1, I] [I – lowbit (I) + 1, I] [I – lowbit (I) + 1, I] the most value.

Update function

void update(int i,int x){
	while(i<=len){
		if(visit[i]){// If I has been accessed, import the visit array to record whether I has been accessed
			C[i]=max(C[i],x);
			/ / or C [I] = min (C [I], x);
		}else{
			C[i]=x;
		}
		i+=lowbit(i);// Next affected I}}Copy the code

Initialization function

void init(a){
	memset(visit,0.sizeof(visit));// Initialize the visit array to 0
	for(int i=1; i<=len; i++){update(i,A[i]);// insert B[I]=A[I] -a [I -1], note that A[0]=0}}Copy the code

Query function

  1. Record C[r]C[r]C[r] each time, and then let r=r−1r=r-1r=r−1, skip to the second step
  2. [r−lowbit(r)+1,r][R −lowbit(r)+1,r][r −lowbit(r)+1,r][r −lowbit(r)+1,r][r −lowbit(r)+1,r][r − Lowbit (r)+1,r][r− Lowbit (r)r=r−lowbit(r) r=r−lowbit(r)r=r −lowbit(r)r=r −lowbit(r) Skip to step 3
  3. Repeat the first step until l=rl=rl=r
int query(int l,int r){
	int M=A[r];
	while(1){
		M=max(M,A[r]);
		/ / or M = min (M, A, [r]).
		if(r==l) break;
		for(r=r- 1; l<=r-lowbit(r); r-=lowbit(r)){// ensure that l is not in the r maintenance interval
			M=max(M,C[r]);
			/ / or M = min (M, C [r]);}}return M;
}
Copy the code