线段树
前缀和一般用于固定的数组
树状数组是一种很高效的数据结构，功能满足大多数的需求
线段树则非常灵活
线段树
线段树是一棵平衡二叉树，满足任意两个子节点的值相加等于父节点。将区间划分为众多的小区间。当a = b则为叶节点
用完全二叉树的算法使用数组进行构造
步骤：
拿到数组，后序创建二叉树
更新
并不是每一个地址都会存放值
但是由于是一颗平衡二叉树，所以，我们的空间至少使用了一半~
struct Node{
int value;//保存的数据
int left;//对应区间的左端点
int right;//对应区间的右端点
};
虽然可以使用指针的方法来构建，但是大多数情况我们使用数组来实现，根据完全二叉树的性质来进行计算。
时间复杂度：
对于存储范围1~N的线段树时间复杂度都是 $O(logn)$
数据插入
void tree_insert(vector<int> &a,int pos, int left, int right, int num){
a[pos]++;
//直接插入到叶节点
if(num == right && num == legt){
return;
}
int mid = (left + right)/2;
int left_child = pos*2 + 2;
if (num<=mid){
tree_insert(a, left_child, left, mid, num);
}else{
tree_insert(a,right_child,mid+1,right,num);
}
}
数据查找
int tree_search(vector<int> &a, int pos, int left, int right, num){
if (num == right && num == left){
return a[pos];
}
int mid = (left+right)/2;
int left_child = pos*2+1;
int right = pos*2+2;
if(num<=mid){
return tree_search(a,left_child,left,mid,num);
}else{
return tree_search(a,left_child,left,mid,num);
}
}
线段树
int main(){
vector<int> a(100,0);//线段树的数组
int left=0;
int right=5;
tree_insert(a,0,left,right,3);
tree_insert(a,0,left,right,5);
tree_insert(a,0,left,right,2);
//print_tree(a,0,left,right);
for(int i=0; i<5;i++){
if(tree_serch(a,0,left,right,i)){
printf("%d is in tree.\n",i);
}
}
}
评论区