算法复习 1.1从最简单的线段树开始 C++

发布时间:2024年01月13日
  1. 思路

  2. 模板图解

对于特殊的区间——单点,单点修改单点查询,那么不那么特殊的怎么办呢

需求:修改和查询->从单点到区间

思路:修改单独一个函数块,查询一个函数块,main录入数据

单点修改,区间查询

例1,在1~9个位置,每个位置放不同数据,1号操作是修改x为y,2号操作是对区间x~y查询,如果暴力,复杂度1操作为1,二操作为每次遍历一个区间长度。n次为n方

如果未学过线段树,又想优化,不妨从基本思路去找,倍增?二分?差分?注意到应当小于n^2,而有n次大概率单次优化到logn就行,联想到二分从中间开始,不断细分

而注意到:查询时,注重的是区间的值而不是每个具体单独的值。

当然也可以一次就分成多段,每段单独暴力(分块)

我们发现直接在原空间上不能完成,所以需要额外存储信息,而又是二分下来的,很容易想到二叉树

我们查找的方式自然想到用左和右以及对应线段的值(取决于需要什么,如区间和)

那么不妨用结构体规范信息,用递归来查找

那么要用二叉树就要先建树存节点

void build(int x,int l,int r){
 tree[i].l=l;tree[i].r=r;
 if(l==r)
 {
 tree[i].sum=in[l];
 }
int mid=(l+r)>>1;
build(i*2,l,mid);
build(i*2+1,mid+1,r);
tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
}

树建好了,如何查呢

就像找零钱一样,多了就退,少了就另加

int search(int i,int l,int r){
  if(tree[i].l>=l&&tree[i].r=r)  return tree.sum;//找到了
  if(tree[i].l>r&&tree[i].r<l)  return 0;//出界
 int t=0;
if (tree[i*2].r>=l) t+=search(i*2,l,r)//找零
if (tree[i*2+1].r>=l) t+=search(i*2+1,l,r)//找零
return t;
}

那么修改怎么修改呢,肯定就不是直接改个值,而是要让所有线段都能用到

从根节点开始添加,直到单个点

void modify(int i,int position,int x){//x修改添加的值
if(tree[i].l==tree[i].r){//找到了
        tree[i].sum+=x;
        return ;
 }
if(position<=tree[i*2].r)  add(i*2,position,x);//在左边
    else  modify(i*2+1,position,x);//在右边
    tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;//返回更新
    return ;
}

每次查询把数据输入进去,数据就出来了

... ...

那么我要是

区间修改,单点查询(1.2)

怎么写呢

单点也是一种区间,那么推广到一般的区间又有何不同呢

区间修改,区间查询(1.3)

以上都是加法,你说减法就加个负号,那么乘除呢,甚至是根号?

计算器都能加减乘除,不妨类比一下

乘法线段树(1.4)


学好线段树就代表你已经度过算法新手区了,应该很厉害吧,试试解决一点点实际问题吧

甲方:你看,普通计算器能算出log呢,ka xi ou 的计算器还能解方程用函数。

那么,区间修改时,计算器每个功能整合到一起应该不难吧

文章来源:https://blog.csdn.net/2302_79123319/article/details/135562537
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。