Tree array explanation

brief introduction

First, let's figure out what tree arrays are for . Now there is a question like this ：
I have an array a, Subscript from 0 To n-1, Now here you are w Time modification ,q Queries , The modification is to modify the value of an element in the array , The query is to query the sum of any interval in the array ,w + q < 500000.

1. Simple approach :
Changes are O (1) Time complexity of , And the query is O (n) Complexity , The overall time complexity is O (qn) ;
2. The prefix and :
The query is O (1) Complexity , When modifying, modify a point , Then all prefixes and in the future should be updated , So the time complexity of modification is O ( n ) The overall time complexity is still O(qn).

You can find , Of the two approaches , Or query yes O(1), Changes are O(n); Or change it to O(1), Query is O ( n ).
So is there a way to combine these two simple ways , Then the overall time complexity can be reduced by an order of magnitude ？ yes , we have , Yes , It's a tree array .

lowbit function

Here, we don't care what the data structure of tree array is , So let's see lowbit This function , You don't need to ask what this function does in tree arrays ;

lowbit The function of this function is to find the lowest bit in the binary representation of a number 1.
 for instance :x = 6, Its binary is 110, that lowbit(x) Just go back to 2, Because the last one 1 Express 2.

The complement of the negative number of a number is equal to the negation of the number +1
Will be decimal -12 Convert to binary 10001100
（ The highest bit represents the symbol , A negative number is 1, A positive number is 0; after 7 Digit value ）
Take the opposite =11110011
then +1 =1111 0100
That is, the complement is 1111 0100
Original code 0000 1100
Complement code 1111 0100
0000 0100

int lowbit(x){
    return x&(-x);}

The principle of tree array

The nature of tree array :
1. Each node stores all the nodes in the subtree that it is the root of Sum of leaf nodes .
2. The number of child nodes of each node is equal to lowbit(x) Number of digits .
3. The parent node of each node except the tree root is x+lowbit(x);

Single point modification , Interval query

Here is the binary version , Can see
The update process is to add a binary low bit each time 1(101+1 ->110, 110 + 10 -> 1000, 1000 + 1000 -> 10000)

Every time the query process is to remove the low bit in the binary 1(1111 - 1 -> 1110, 1110 - 10 -> 1100, 1100 - 100 -> 1000)

Single point update :

void add(int x, int k) {
    
  while (x <= n) {
      //  Don't cross the border 
    tree[x] = tree[x] + k;
    x = x + lowbit(x);
  }
}

Prefix summation

int getsum(int x) {
      // a[1]..a[x] And 
  int ans = 0;
  while (x >= 1) {
    
    ans = ans + tree[x];
    x = x - lowbit(x);
  }
  return ans;
}

Sum of intervals

int queary(int l,int r){
    
	return getsum(r)-getsum(l-1);
}

Be careful ：lowbit(0)=0, therefore x=0 when ,x+=lowbit(x) or x-=lowbit(x),x Still 0.

Interval modification + Single point query

An interval is modified to a certain interval [x,y] Add a value at the same time , Then query the value of a point , Or the value of an interval . At this time, it is necessary to make a difference .

 Original array        1 2 3 3   2  1
 Difference array      1 1 1 0  -1 -1

Differential array interval [1,x] The prefix and , It's the original array x Single point value of , For interval modification, you only need to modify a single point x and y+1.
for example ： Section [2,4] Add 2

 Updated array 	:  1 4 5 5  2  1
 Updated difference score group : 1 3 1 0 -3 -1
 Original difference fraction group       1 1 1 0  -1 -1
 We find that the difference array has only 2 and 5 The position of the has changed 

void add(int x, int k){
     // This function is used to modify... Directly in the tree array 
    while(x <= n) tree[x] += k, x+=lowbit(x);
}
void range_add(int l, int r, int x){
     // Give interval [l, r] add x
    add(l, x), add(r + 1, -x);
}
int ask(int x){
     // Single point query 
    int res = 0;
    while(x) res +=tree[x], x-=lowbit(x);
    return res;
}
void read(){
    
	for(int i=1;i<=n;i++){
    
		scanf("%d",&a[i]);
		add(i,a[i]-a[i-1]);
	}
}

Interval modification + Interval query

From the top , Differential array interval [1,x] The prefix and , It's the original array x Single point value of . Original interval [1,x] And ：

 Updated array 	:  1 4 5 5  2  1
 Updated difference score group : 1 3 1 0 -3 -1
 such as ： We ask for the interval [1,3] And , We found that the first position used 3 Time , The second position uses 2 Time , The third position uses 1 Time .
 We can multiply each position by x( ad locum x=3), And then subtract (i-1)*a[i] individual .

Equivalent to maintenance 2 A tree array. One is a[i], The other is b[i]=(i-1)*a[i].

void add(int x,int t){
    
	int k=x;
	while(x<=n){
    
	a[x]+=t;
	b[x]+=(k-1)*t;
	x+=lowbit(x);
	}
}
int query(int x)
{
    
	int ans=0,k=x;
	while(x>0){
    
	ans+=k*a[i]-b[i];
	x-=lowbit(x);
	}
	return ans;
}
void range_add(int l, int r, int x){
    
    add(l, x), add(r + 1, -x);
}

 Be careful : The operation range exceeds int You should use long long;