This is the sixth day of my participation in Gwen Challenge

A tree array, as the name suggests, is an array that looks like a tree, but it’s stored like a tree, just like a hash table is stored according to a hash function.

How exactly do you deposit it? Define the C[] array at the top of each column

In the figure, C[I] represents the sum of the weights of the leaf nodes of the subtree // Here, the maintenance interval sum is taken as an example.

C[1]=A[1];

C[2]=A[1]+A[2];

C[3]=A[3];

C[4]=A[1]+A[2]+A[3]+A[4];

C[5]=A[5];

C[6]=A[5]+A[6];

C[7]=A[7];

C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8];

This is what C[I] stands for. We’re essentially storing the sum of intervals on a full binary tree, why do we do that

That’s where the Lowbit function comes in.

Lowbit function int lowbit(int x) {return x&(-x); } #define lowbit(x) x&(-x) // It is used as the result of “binary number from the lowest digit to the highest digit, the first digit 1”. Lowbit (12) = 4 (1) lowbit(12) = 4 (1) So that’s the magic of binary and bit operations. At the beginning, it may be difficult to accept and understand. But it’s getting there.

Now that we know what this function is, if we look at the following, we can see why we have a full binary tree, right

Convert the node number of the C[] array to binary

1=(001)      C[1]=A[1];

2=(010)      C[2]=A[1]+A[2];

3=(011)      C[3]=A[3];

4=(100)      C[4]=A[1]+A[2]+A[3]+A[4];

5=(101)      C[5]=A[5];

6=(110)      C[6]=A[5]+A[6];

7=(111)      C[7]=A[7];

8=(1000)    C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8];

C[I]=A[I -2^k+1]+A[I -2^k+2]+…… A[i]; (the length of consecutive zeros from lowest to highest in the binary system where k is I) for example, if I =8, k=3;

 

(I, i-lowbit (I) +1); (I, i-lowbit (I) +1); (I, i-lowbit (I) +1); (I, i-lowbit (I) +1)

The sum of the interval [1, x], since [x, y] =[1, y] – [1, x], we can easily obtain the sum of any interval.

The function for Sum[] is given here.

int sum(int c[],int i){
    int s=0;
    while(i>0){
        s+=c[i];
        i-=lowbit(i);
    }
    return s;
}
Copy the code

Interval maintenance after single point update; Let’s just go to the code. It’s not hard to understand.

void updata(int i, int val)
{
	while (i <= n)
	{
		c[i] += val;
		i += lowbit(i); }}Copy the code

Now let’s talk about interval maximum query and maintenance. Interval maxima and interval sum are not the same, but they are roughly the same in idea.

In the algorithm for maximizing intervals, h[x] is used to store the maximum value of each number in [x, x-lowbit(x)+1].

The algorithm that maximizes the interval also has an array of a[I], which tells you what the ith number is.

 

Interval maximum query: there is no way to copy the interval sum method,

Query (x,y) {h[y] = [y,y +1];

then

Query (x,y) = Max (h[y], query(x, y-lowbit(y)));

If y – lowbit (y) < = x, then the query (x, y) = Max ([y], a query (x, y – 1);

We’re going to do it recursively, and in code, we’re going to do it recursively. If you understand these two formulas, you’re pretty much done.

int query(int x, int y)
{
	int ans = 0;
	while (y >= x)
	{
		ans = max(a[y], ans);
		y --;
		for (; y-lowbit(y) >= x; y -= lowbit(y))
			ans = max(h[y], ans);
	}
	return ans;
}
Copy the code

Updated interval maintenance

void updata(int x,int data)
{
	
	while (x <= n)
	{
		h[x] = data;// Start maintenance from the left
		for (int i=1; i<lowbit(x); i<<=1)
			h[x] = max(h[x], h[x-i]);
		x += lowbit(x); }}Copy the code

​