最好下标从0开始
by szr666 @ 2019-07-18 11:21:00
最好下标从0开始
by szr666 @ 2019-07-18 11:21:30
写成build(0,n-1)
2*k+1 2*k+2
by szr666 @ 2019-07-18 11:21:55
@[szr666](/space/show?uid=129849)
习惯了。。。这个不影响啊
by Mr__Meng @ 2019-07-18 11:22:19
我以前用你那个就错了
也不知道怎莫
by szr666 @ 2019-07-18 11:23:09
@[1596093267ybd](/space/show?uid=112604) 开头加一句
```
memset(mi,0x7f,sizeof(mi));
```
by SSerxhs @ 2019-07-18 11:24:29
@[1596093267ybd](/space/show?uid=112604) 诶好像不用。。不太清楚，没写过这样的线段树
by SSerxhs @ 2019-07-18 11:25:20
@[szr666](/space/show?uid=129849)
这个标程跟我的有区别吗。。。
```c
#include<cstdio>
#include<iostream>
#include<algorithm>
#define maxn 1000005
using namespace std;
int dist[maxn];
int n,m;//n points m asking
void build_tree(int k,int l,int r,int x,int v){
if(l>x||r<x)return;
if(l==r&&l==x){
dist[k]=v;return;
}
int mid=(l+r)>>1;
build_tree(k<<1,l,mid,x,v);
build_tree((k<<1)+1,mid+1,r,x,v);
dist[k]=min(dist[k<<1],dist[(k<<1)+1]);
}
int ask_query(int k,int l,int r,int x,int y){
if(l>y||r<x)return 0x3f3f3f;
if(l>=x&&r<=y)return dist[k];
int mid=(l+r)>>1;
return min(ask_query(k<<1,l,mid,x,y),ask_query((k<<1)+1,mid+1,r,x,y));
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
int temp;
scanf("%d",&temp);build_tree(1,1,n,i,temp);
}
for(int i=1;i<=m;i++){
int left,right;
scanf("%d%d",&left,&right);
printf("%d\n",ask_query(1,1,n,left,right));
}
return 0;
}
```
by Mr__Meng @ 2019-07-18 11:25:24
你看一下我的吧
P3372 【模板】线段树 1
```cpp
#include<cstdio>
#define ls (((now)*2)+1)
#define rs (((now)*2)+2)
#define mid (((l)+(r))/2)
#define ll long long
using namespace std;
void read(int &x)
{
x=0;
int f;
f=1;
char c;
c=getchar();
while((c<'0'||c>'9')&&c!='-')
{
c=getchar();
}
if(c=='-')
{
f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
x=x*f;
}
void read(ll &x)
{
x=0;
ll f;
f=1;
char c;
c=getchar();
while((c<'0'||c>'9')&&c!='-')
{
c=getchar();
}
if(c=='-')
{
f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
x=x*f;
}
struct node
{
ll sum;
ll pls;
};
node sqt[500000];
ll a[200000];
int max(int x1,int x2)
{
return x1>x2 ? x1 : x2;
}
int min(int x1,int x2)
{
return x1<x2 ? x1 : x2;
}
void update(int now)
{
sqt[now].sum=sqt[ls].sum+sqt[rs].sum;
sqt[now].pls=0;
}
void build(int now,int l,int r)
{
if(l==r)
{
sqt[now].sum=a[l];
sqt[now].pls=0;
}
else
{
build(ls,l,mid);
build(rs,mid+1,r);
update(now);
}
}
void plusdown(int now,int l,int r)
{
sqt[now].sum+=sqt[now].pls*(r-l+1);
sqt[ls].pls+=sqt[now].pls;
sqt[rs].pls+=sqt[now].pls;
sqt[now].pls=0;
}
ll query(int now,int l,int r,int x,int y)
{
if(sqt[now].pls!=0)
{
plusdown(now,l,r);
}
if(x==l&&y==r)
{
return sqt[now].sum;
}
else if(y<=mid)
{
return query(ls,l,mid,x,y);
}
else if(x>mid)
{
return query(rs,mid+1,r,x,y);
}
else
{
return query(ls,l,mid,x,mid)+query(rs,mid+1,r,mid+1,y);
}
}
void querypls(int now,int l,int r,int x,int y,ll val)
{
if(l==x&&r==y)
{
sqt[now].pls+=val;
}
else if(y<=mid)
{
sqt[now].sum+=val*(min(y,r)-max(x,l)+1);
querypls(ls,l,mid,x,y,val);
}
else if(x>mid)
{
sqt[now].sum+=val*(min(y,r)-max(x,l)+1);
querypls(rs,mid+1,r,x,y,val);
}
else
{
sqt[now].sum+=val*(min(y,r)-max(x,l)+1);
querypls(ls,l,mid,x,mid,val);
querypls(rs,mid+1,r,mid+1,y,val);
}
}
int main()
{
int n,m,i,k,x,y,v;
read(n);
read(m);
for(i=0;i<n;i++)
{
read(a[i]);
}
build(0,0,n-1);
for(i=1;i<=m;i++)
{
read(k);
if(k==1)
{
read(x);
read(y);
read(v);
querypls(0,0,n-1,x-1,y-1,v);
}
else if(k==2)
{
read(x);
read(y);
printf("%lld\n",query(0,0,n-1,x-1,y-1));
}
}
}
```
by szr666 @ 2019-07-18 11:27:32
好像没有
by szr666 @ 2019-07-18 11:28:05