线段树

1.pushup: 用子节点信息来更新当前节点信息
2.build:在一段区间上初始化线段树
3.modif:修改
4.query:查询
5. 对于坐标x,x/2为父节点,x<<1为左子节点,x<<1|1为右子节点
#include<iostream>
using namespace std;
int n,m;
const int N=100010;
int a[N];
struct tree{
	int l;
	int r;
	int sum;
}tr[4*N];
void push_up(int u)
{
	tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;//更新区间和
}
int build(int u,int l,int r)
{
	if(l==r)tr[u]={l,r,a[r]};
	else {
		int m=l+r>>1;
		tr[u]={l,r};//给节点赋初值
		build(u<<1,l,m);
		build(u<<1|1,m+1,r);
		push_up(u);
	}
}
int query(int u,int l,int r)
{
	if(tr[u].l>=l&&tr[u].r<=r)return tr[u].sum;//如果该区间(l,r)被tr[u]包含就返回tr[u].sum;
    int m=tr[u].l+tr[u].r>>1;
    int sum=0;
    if(l<=m)sum+=query(u<<1,l,r);//判断一下该区间左端点是不是在tr[u]区间的左半边
    if(r>=m+1)sum+=query(u<<1|1,l,r);//
    return sum;
}
void modif(int u,int x,int v)
{
	if(tr[u].r==tr[u].l)tr[u].sum+=v;//如果是叶节点直接加上v
        //否则的话就判断一下,哪些区间需要加上v
	else{
		int m=tr[u].l+tr[u].r>>1;
		if(x<=m)
		{
			modif(u<<1,x,v);
		}
        else
		{
			modif(u<<1|1,x,v);
		}
		push_up(u);
	}

}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	build(1,1,n);
	while(m--)
	{
		int k,x,y;
		cin>>k>>x>>y;
		if(k==0){
			cout<<query(1,x,y)<<endl;
		}
		else {
			modif(1,x,y);
		}
	}
	return 0;
}


全部评论

相关推荐

03-15 00:45
已编辑
高德地图_go开发(实习员工)
问的很简单都秒了,但是面试官没开摄像头,疑似kpi,无后续。--------------------3/14更新,3/12通知给了口头offer,3/13发了意向书,已拒。一面(35min)(25/3/6)(无后续)&nbsp;&nbsp;&nbsp;&nbsp;1、自我介绍&nbsp;&nbsp;&nbsp;&nbsp;2、介绍一下你的那个Python相关项目(本科毕设,web系统+算法模型提供部分接口)&nbsp;&nbsp;&nbsp;&nbsp;3、Java面向对象有哪些特点呢?详细说一下。&nbsp;&nbsp;&nbsp;&nbsp;4、介绍一下hashmap;为什么要把链表转换为红黑树呢?红黑树查找的时间复杂度?1.7和1.8的区别。&nbsp;&nbsp;&nbsp;&nbsp;5、介绍一下concurrentHashmap。&nbsp;&nbsp;&nbsp;&nbsp;6、synchronized锁和Lock锁有什么区别?&nbsp;&nbsp;&nbsp;&nbsp;7、公平锁的一个底层是怎么实现的呢?&nbsp;&nbsp;&nbsp;&nbsp;8、线程池的核心参数、拒绝策略、提交一个任务执行流程?&nbsp;&nbsp;&nbsp;&nbsp;9、spring有哪些特点?(ioc/aop)&nbsp;&nbsp;&nbsp;&nbsp;10、spring中对于循环依赖是怎么解决的?&nbsp;&nbsp;&nbsp;&nbsp;11、MySQL和redis的区别?&nbsp;&nbsp;&nbsp;&nbsp;12、MySQL的索引结构是什么?&nbsp;&nbsp;&nbsp;&nbsp;13、MySQL的事务有哪些特性?怎么保证?&nbsp;&nbsp;&nbsp;&nbsp;14、MySQL的默认隔离级别?可重复读是怎么做到的呢?&nbsp;&nbsp;&nbsp;&nbsp;15、介绍一下MVCC和快照读readview。&nbsp;&nbsp;&nbsp;&nbsp;16、一般在什么场景下会使用redis?&nbsp;&nbsp;&nbsp;&nbsp;17、对于大量的请求,如果此时缓存中还没有写入数据怎么办?&nbsp;&nbsp;&nbsp;&nbsp;18、介绍一下redis实现的分布式锁。&nbsp;&nbsp;&nbsp;&nbsp;19、有用过es和mongo&nbsp;DB吗?(知道,没用过)&nbsp;&nbsp;&nbsp;&nbsp;20、消息中间件用过吗?说一下你的使用场景?&nbsp;&nbsp;&nbsp;&nbsp;21、一个场景,如果说有一个接口响应的比较慢,如果说让你排查,你会怎么去排查?(上下游接口、大key问题,只答了两,后面试官补充)&nbsp;&nbsp;&nbsp;&nbsp;无手撕,反问业务。
胖墩墩的查理在学c语言:哥们我是五号面的 流程差不多
查看21道真题和解析
点赞 评论 收藏
分享
02-25 11:29
产品经理
牛客444597598号:兄弟 我只能说如果想找产品经理这种简历 基本就是毕业失业了 你这连实习都找不到的 简历跟产品经理一点都没有关系,你可以去搜搜产品的模版吧
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务