洛谷日报
by xh39 @ 2020-02-14 22:14:38
@[无敌的蒟蒻](/user/151647) 铜球
by SMT0x400 @ 2020-02-14 22:14:53
@[i_am_aking_ioi](/user/87799) 求网址
by sycqwq @ 2020-02-14 22:15:39
[洛谷日报#4](https://www.luogu.com.cn/blog/pks-LOVING/senior-data-structure-qian-tan-xian-duan-shu-segment-tree)
by xh39 @ 2020-02-14 22:17:25
@[i_am_aking_ioi](/user/87799) 要内容更多的
by sycqwq @ 2020-02-14 22:19:25
@[无敌的蒟蒻](/user/151647) "区间最大子段和" 直接做 小白逛公园 就好了吧
by DepletedPrism @ 2020-02-14 23:00:27
@[无敌的蒟蒻](/user/151647) [这个](https://www.cnblogs.com/jason2003/p/9676729.html)我觉得不错
by liqingyang @ 2020-02-14 23:13:06
这是我单点修改最大值的代码
```cpp
#include<iostream>
using namespace std;
const long long oo=(long long)1e18;
long long a[300010];
int n,m;
void update(int s)
{
a[s]=max(a[s*2],a[s*2+1]);
}
void biuld(int l,int r,int s)
{
if(l==r)
{
cin>>a[s];
return;
}
int mid=(l+r)/2;
biuld(l,mid,s*2);
biuld(mid+1,r,s*2+1);
update(s);
}
void change(int l,int r,int s,int x,long long y)
{
if(r<x||l>x)
{
return;
}
if(x==l&&x==r)
{
a[s]=y;
return;
}
int mid=(l+r)/2;
change(l,mid,s*2,x,y);
change(mid+1,r,s*2+1,x,y);
update(s);
}
long long q(int l,int r,int ll,int rr,int s)
{
if(r<ll||l>rr)
{
return -oo;
}
if(ll<=l&&r<=rr)
{
return a[s];
}
int mid=(l+r)/2;
return max(q(l,mid,ll,rr,s*2),q(mid+1,r,ll,rr,s*2+1));
}
int main()
{
freopen("max.in","r",stdin);
freopen("max.out","w",stdout);
cin>>n;
biuld(1,n,1);
cin>>m;
for(int i=1;i<=m;i++)
{
int flag,x;
long long y;
cin>>flag>>x>>y;
if(flag==1)
{
change(1,n,1,x,y);
}
else
{
cout<<q(1,n,x,y,1)<<endl;
}
}
return 0;
}
```
by liqingyang @ 2020-02-14 23:15:22
然后你可以试着做做[这个](https://www.luogu.com.cn/problem/P3372)和[这个](https://www.luogu.com.cn/problem/P2234)
等你再厉害一点了再做[这个](https://www.luogu.com.cn/problem/P3373)
by liqingyang @ 2020-02-14 23:18:05
这是我多点修改最大值的代码
```cpp
#include<iostream>
#include<algorithm>
using namespace std;
const long long oo=(long long)1e18;
struct tree
{
long long x;
int ss;
};
tree a[300010];
int n,m;
void update(int s)
{
a[s].x=max(a[s*2].x,a[s*2+1].x);
}
void pushdown(int s)
{
if(a[s].ss)
{
a[s*2].ss+=a[s].ss;
a[s*2+1].ss+=a[s].ss;
a[s*2].x+=a[s].ss;
a[s*2+1].x+=a[s].ss;
a[s].ss=0;
}
}
void biuld(int l,int r,int s)
{
if(l==r)
{
cin>>a[s].x;
return;
}
int mid=(l+r)/2;
biuld(l,mid,s*2);
biuld(mid+1,r,s*2+1);
update(s);
}
void add(int l,int r,int ll,int rr,int c,int s)
{
if(r<ll||l>rr)
{
return;
}
if(ll<=l&&r<=rr)
{
a[s].x+=c;
a[s].ss+=c;
return;
}
pushdown(s);
int mid=(l+r)/2;
add(l,mid,ll,rr,c,s*2);
add(mid+1,r,ll,rr,c,s*2+1);
update(s);
}
long long getans(int l,int r,int ll,int rr,int s)
{
if(r<ll||l>rr)
{
return -oo;
}
if(ll<=l&&r<=rr)
{
return a[s].x;
}
pushdown(s);
int mid=(l+r)/2;
return max(getans(l,mid,ll,rr,s*2),getans(mid+1,r,ll,rr,s*2+1));
}
int main()
{
ios::sync_with_stdio(false);
cin>>n;
biuld(1,n,1);
cin>>m;
for(int i=1;i<=m;i++)
{
int flag,x,y;
cin>>flag>>x>>y;
if(flag==1)
{
int v;
cin>>v;
add(1,n,x,y,v,1);
}
else
{
cout<<getans(1,n,x,y,1)<<endl;
}
}
return 0;
}
```
by liqingyang @ 2020-02-14 23:18:47