关于线段树修改点的问题
  • 板块学术版
  • 楼主Dino_chx
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/9/3 12:47
  • 上次更新2023/10/27 12:43:56
查看原帖
关于线段树修改点的问题
715233
Dino_chx楼主2022/9/3 12:47

蒟蒻刚刚学会线段树,可是码力只限于线段树的加法。请大佬们指出一些线段树修改的点呗~

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
#define f 1LL
using namespace std;
const int N=1e5+5;
ll tree[N<<2],lz[N<<2];
inline int read()
{
int c=1,k=0;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
c=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
k=(k<<3)+(k<<1)+(ch^48);
ch=getchar();
}
return c*k;
}
inline int getmid(int l,int r)
{
return l+((r-l)>>1);
}
inline int lc(int x)
{
return x<<1;
}
inline int rc(int x)
{
return x<<1|1;
}
inline void push_up(int x)
{
tree[x]=tree[lc(x)]+tree[rc(x)];
return;
}
inline void init()
{
memset(tree,0,sizeof tree);
memset(lz,0,sizeof lz);
return;
}
//build 建树 
void build(int data,int l,int r)    //l r 管辖范围
{
if(l==r)
{
tree[data]=read();
return;
}
int mid=getmid(l,r);
build(lc(data),l,mid);
build(rc(data),mid+1,r);
push_up(data);
return;
} 
//push_down 懒标记下传 
void push_down(int data,int l,int r)
{
if(lz[data])
{
int mid=getmid(l,r);
lz[lc(data)]+=lz[data];
lz[rc(data)]+=lz[data];
tree[lc(data)]+=f*(mid-l+1)*lz[data];
tree[rc(data)]+=f*(r-mid)*lz[data];
lz[data]=0;
}
return;
}
//update 单点更新 
void update(int data,int l,int r,int k,int index)
{
if(l==r)
{
tree[data]+=k;       //自由更新 
return;
}
int mid=getmid(l,r);
push_down(data,mid-l+1,r-mid);
if(index<=mid)
update(lc(data),l,mid,k,index);
else
update(rc(data),mid+1,r,k,index);
push_up(data);
return;
}
//update_range 区间更新 
void update_range(int data,int l,int r,int tl,int tr,int k)
{
if(l<=tl&&r>=tr)
{
lz[data]+=f*k;
tree[data]+=f*(tr-tl+1)*k;
return;
}
push_down(data,tl,tr);
int mid=getmid(tl,tr);
if(mid>=l)
update_range(lc(data),l,r,tl,mid,k);
if(mid<r)
update_range(rc(data),l,r,mid+1,tr,k);
push_up(data);
return;
}
//query_range 区间求和 
ll query_range(int data,int l,int r,int tl,int tr)
{
if(l<=tl&&r>=tr)
return tree[data];
push_down(data,tl,tr);
int mid=getmid(tl,tr);
ll ans=0;
if(mid>=l)
ans+=query_range(lc(data),l,r,tl,mid);
if(mid<r)
ans+=query_range(rc(data),l,r,mid+1,tr);
return ans;
}
int main()
{

return 0;
}
2022/9/3 12:47
加载中...