Tree array and St table

Tree array and ST surface

dynamic ： Tree array static state ：ST surface
Tree array ：cnt=x End of binary 0 The number of , Array d[x] Store 2^cnt Number .
Inquire about ： such as 13,13 = 1101, Only one number is stored a[13], Now? , seek 13 The prefix of this position and ：
( There are several 1 Divided into several parts ) Divided into three parts : ( Every time, the last one is erased 1,log Grade )
1101 d[13] 2^0
1100 d[12] 2^2
1000 d[8] 2^3
Single query complexity logn
modify ： Modify the value of a node , You need to modify the value of the node that overrides him .
How to get the last end 1 Where is the location ？（ principle , Complement or something ）
Lowbit(int x){// Returns the... At the end of the binary 1 Where is the
return x & (-x);
}
summary ： The query subtracts 1, Modify to add 1.
To solve ： Interval query （ Prefixes and ideas ）, Single point modification （lowbit Keep looking for his points to cover ）

#include <stdio.h>
#include <string>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <set>
#include <queue>
#include <math.h>
#include <map>
#include <bitset>
#include <stdlib.h>
#include <vector>
using namespace std;
typedef long long ll;
#define pb push_back
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;

/******** Single point modification , Interval query **********/
int lowbit(int x){
    
	return x & (-x);
}

int ask(int x){
    //[1, x], Satisfy prefix and 
	int res = 0;
	while(x){
    
		res += d[x];
	}
	x -= lowbit(x);
	return res;
}

void add(int x, int v){
    
	while(x <= n){
    
		d[x] += v;
		x += lowbit(x);
	}
}

/********** Two dimensional tree array single point modification , Interval query ****************/
void update(int x, int y, int v){
    
	for( ; x <= n; x += lowbit(x)){
    
		for(int j = y; j <= n; j += lowbit(j)){
    
			d[x][j] += v;
		}
	}
}

int getsum(int x, int y){
    
	int res = 0;
	for( ; x > 0; x -= lowbit(x)){
    
		for(int j = y; j; j -= lowbit(j)){
    
			res += d[x][j];
		}
	}
	return res;
}


int main(){
    

	return 0;
}

Single point query , Interval modification （ Difference thinking ）
Maximum / Small value （ The segment tree is better , It's just that the constant is a little larger ,ST The watch is OK, too ）
cf755D poj2352 bzoj1878 bzoj2743 bzoj1452
Two dimensional tree array
ST surface ：RMQ problem
Line segment tree ：O（n) Preprocessing Single inquiry O(logn) Space O(n)
ST surface ：O(nlogn) Preprocessing Single inquiry O(1) Space O(nlogn)
d[i][j] An organization representing such a range ： The left endpoint is i, The length is 2^j, signify , It governs [i,i + 2^j - 1]
CDOJ1591(ST surface )