首页 > 编程知识 正文

一个有效的算法有哪些特点(算法的特性有)

时间:2023-05-03 12:36:30 阅读:95986 作者:4213

部分图片来源于网络,被入侵删除!

熊猫人线段树

什么是线段树

入门算法的同学一定要熟悉数据结构的线段树。线段树也是算法竞争中有效求解区间的一种非常重要的方法。线树是二叉查找树树,类似于区间树。它将一个区间划分为单位区间,每个单位区间对应于行树中的一个叶节点。下面我将详细介绍线段树的基本方法。

00-1010线段树是二叉查找树。什么是二叉查找树?首先满足二叉树,每个节点的度小于等于2,即每个节点最多有两个子树。什么是搜索?我们需要知道线段树的每个节点都存储了一个区间,这个区间也可以理解为一个线段。搜索就是在这些线段上搜索,得到你想要的答案。

构建线段树的时间复杂度是O(N)(不是O(nlogn))!线段树可以用来快速查找一个节点在几个线段中出现的次数,查找的时间复杂度为O(logN)。未优化的空间复杂度为O(2N),因此有时需要离散化来压缩空间。

线树采用分治的思想(主要是二分法),一般可以高效地解决区间问题。线树的叶节点是最简单的节点,叶节点的父节点是两个叶节点的区间的并集。对于线段树中的每个非叶节点[a,b],其左子节点代表区间[a,(a b)/2],其右子节点代表区间[(a b)/2 1,b]。因此线段树是一个平衡二叉树,最终节点数为n,即整个线段区间的长度。区间[1-5]的段树如下图所示。

1到5范围内的分段树

线段树的概念

如上所述,线段树可以高效解决区间问题,那么具体流程是怎样的呢?

你可以先看一下这个经典段落树的问题,我稍后会把问题发到推文中。

链接:http://acm.hdu.edu.cn/showproblem.php? Pid=1166(内容中不能引用国外网站链接,我会放在下面)

打开后会发现,这个题目是典型的区间处理题目,但是数据范围极大,要处理各种操作,直接用数组存储和遍历会直接超时。那么线段树(快捷方便)就派上用场了。段树主要处理广泛的区间运算。

00-1010线段树的定义父节点的val值是所有子节点值的和,有利于后面的操作,叶节点的值是区间中输入的值。

结构Nd //定义段树的节点。

{

int left//左孩子

int right//右孩子

int val//节点值

};取得成就

通过递归构建树是一种常见的操作。当r==l时,表示到达叶节点。终于逮捕了[我]。val=arr [i1]。valarr [i1 | 1]。瓦尔;子节点到父节点的分配是在递归回溯期间完成的,因此父节点的val值是子节点所有值的总和。X1和x1|1等价于x*=2和x=x*2 1。分别寻找两个子节点。如下图所示。

父节点对应于子节点。

Void build(int l,int r,int i)//通过递归构造线段树

{

arr[i]。左=l;//将左右间隔的值分配给节点。

arr[i]。右=r;

if(r==l)

{

std:cin arr[i]。瓦尔;//最后一个叶节点存储要存储的值。

返回;

}

build(l,(l r)/2,i1);//递归到左节点

build((r l)/2 1,r,i1 | 1);//递归到右节点

arr[i]。val=arr[i1]。val arr[i1|1]。瓦尔;//递归回溯时,完成子节点到父节点的赋值。

}arr[i]。val=arr[i1]。val arr[i1|1]。瓦尔;完美时间的值是下面所有节点(相关)的总和,递归是从深到浅,从左到右(变量左和右)遍历的过程(DFS就是这样)。

3.DFS打印树

这样方便看到树的每一个节点以及是否有声音,方便发现bugs ~

作废dfs_print

(int l,int r,int i) { /*if(r==l) { std::cout << arr[i].val << ' ';//打印叶子节点 return ; }*/ std::cout << arr[i].val << ' '; if(r==l) { return ; } dfs_print(l,(l+r)/2,i<<1); dfs_print((r+l)/2+1,r,i<<1|1); }

4.更新节点

arr[d].left==arr[d].right时就是叶子,别忘了对父节点回溯时的刷新值。递归找叶节点后更改,

void update(int d,int r,int b)// d为当前节点 r为更新的节点 b为改变节点的值 这个递归算法实际就是二分查找 { if(arr[d].left==arr[d].right)//递归到叶子节点时 肯定下标是r 注意只能更改叶子节点 { arr[d].val=b;//更改值 return; } int mid = (arr[d].left+arr[d].right)>>1; if(r>mid)update(d<<1|1,r,b);//递归到右son else update(d<<1,r,b);//递归到左son arr[d].val = arr[d<<1].val+arr[d<<1|1].val;//递归回溯时完成子节点对父节点的赋值 }

5.区间查询(返回区间内所有节点和)

将范围一步一步划分小,充分利用父节点的值增加效率。

//区间查询 我们不要忘记,父节点可是存储着它俩儿子值的和 int query(int d,int l,int r)//这个是返回区间的和 { int sum = 0;//区间总和 if(l==arr[d].left&&r==arr[d].right)//1.如果在目的范围内的父亲节点 可以增加效率 sum += arr[d].val; else{ int mid = ((arr[d].left+arr[d].right)/2); if(l<=mid) (r>mid)?sum+=query(d<<1,l,mid):sum+=query(d<<1,l,r); if(r>mid) (l<=mid)?sum+=query(d<<1|1,mid+1,r):sum+=query(d<<1|1,l,r); } return sum; }

父节点存储所有子节点的总值,所以我们只需查找范围内的父节点即可。可能您不明白9到12行代码的意义以及如何利用父节点查找:请看下面的图片

分割操作

虽然图片只有两种情况,别忘了有左右两个子节点,所有必须有四个if判断(代码中部分用三目式代替)。当l==arr[d].left&&r==arr[d].right(分割的目的范围与节点范围相同时返回值)

6.单节点查询

其实直接调用区间查询即可,两个范围一样就是单节点,这样效率不会影响,还是O(logn)

//单点查询 直接调用区间查询即可 效率不受影响 int find(int d,int o)//d 为当前节点 o为查询节点 { return query(d,o,o); }

7.区间修改

8-12行代码原理如上图所示。将区间范围一步一步划分为节点操作,这样只需要一个递归就可以解决,具有很高的效率,别忘了父节点的值。

void changeSegment(int d,int l,int r,int x)//l和r是修改的范围 x是范围内每一个节点改变的值 { if(arr[d].left==l&&arr[d].right==r&&arr[d].left==arr[d].right){//一定要修改叶子节点 不要误修改父节点 arr[d].val+=x; return ; }else{ int mid = ((arr[d].left+arr[d].right)/2); if(l<=mid) (r>mid)?changeSegment(d<<1,l,mid,x):changeSegment(d<<1,l,r,x); if(r>mid) (l<=mid)?changeSegment(d<<1|1,mid+1,r,x):changeSegment(d<<1|1,l,r,x); arr[d].val = arr[d<<1].val+arr[d<<1|1].val;//回溯 改变父节点的值 } }

测试总代码

#include <bits/stdc++.h> struct Nd //定义线段树节点 { int left;//左孩子 int right;//右孩子 int val;//该节点值 }; Nd arr[1 << 10]; //随便设有1024个节点 //初始化 void build(int l,int r,int i)//利用递归构成线段树 { arr[i].left=l;//将左右区间的值赋值给节点 arr[i].right=r; if(r==l) { std::cin >> arr[i].val; return ; } build(l,(l+r)/2,i<<1);//递归到左节点 build((r+l)/2+1,r,i<<1|1); //递归到右节点 arr[i].val = arr[i<<1].val+arr[i<<1|1].val;//递归回溯时完成子节点对父节点的赋值 } //打印节点 void dfs_print(int l,int r,int i) { /*if(r==l) { std::cout << arr[i].val << ' ';//打印叶子节点 return ; }*/ std::cout << arr[i].val << ' '; if(r==l) { return ; } dfs_print(l,(l+r)/2,i<<1); dfs_print((r+l)/2+1,r,i<<1|1); } //更新节点 void update(int d,int r,int b)// d为当前节点 r为更新的节点 b为改变节点的值 这个递归算法实际就是二分查找 { if(arr[d].left==arr[d].right)//递归到叶子节点时 肯定下标是r 注意只能更改叶子节点 { arr[d].val=b;//更改值 return; } int mid = (arr[d].left+arr[d].right)>>1; if(r>mid)update(d<<1|1,r,b);//递归到右son else update(d<<1,r,b);//递归到左son arr[d].val = arr[d<<1].val+arr[d<<1|1].val;//递归回溯时完成子节点对父节点的赋值 } //区间查询 我们不要忘记,父节点可是存储着它俩儿子值的和 int query(int d,int l,int r)//这个是返回区间的和 { int sum = 0; if(l==arr[d].left&&r==arr[d].right)//1.如果在目的范围内 sum += arr[d].val; else{ int mid = ((arr[d].left+arr[d].right)/2); if(l<=mid) (r>mid)?sum+=query(d<<1,l,mid):sum+=query(d<<1,l,r); if(r>mid) (l<=mid)?sum+=query(d<<1|1,mid+1,r):sum+=query(d<<1|1,l,r); } return sum; } //单点查询 直接调用区间查询即可 效率不受影响 int find(int d,int o)//d 为当前节点 o为查询节点 { return query(d,o,o); } void changeSegment(int d,int l,int r,int x) { if(arr[d].left==l&&arr[d].right==r&&arr[d].left==arr[d].right){ arr[d].val+=x; return ; }else{ int mid = ((arr[d].left+arr[d].right)/2); if(l<=mid) (r>mid)?changeSegment(d<<1,l,mid,x):changeSegment(d<<1,l,r,x); if(r>mid) (l<=mid)?changeSegment(d<<1|1,mid+1,r,x):changeSegment(d<<1|1,l,r,x); arr[d].val = arr[d<<1].val+arr[d<<1|1].val; } } int main() { using namespace std; build(1,5,1); dfs_print(1,5,1); int n,a,x; cin >> n >> a >> x; /*update(1,n,a); dfs_print(1,5,1); cout << endl; cin >> n >> a; cout << "sum=" << query(1,n,a)<<endl; cin >> n; cout << find(1,n);*/ changeSegment(1,n,a,x); dfs_print(1,5,1); return 0; }

感谢

感谢观看,希望大家能够尽情的指点,如果有什么错误的地方可以指出来。

创作不易,如果大家感觉有帮助请点一下赞,谢谢。

下回会更新它的一道例题题解,链接如下所示。

版权声明:该文观点仅代表作者本人。处理文章:请发送邮件至 三1五14八八95#扣扣.com 举报,一经查实,本站将立刻删除。