考试总结

int Query(int rt,int l,int r)//查询区间和
{ 
        if(l<=tree[rt].l&&tree[rt].r<=r)
	        return tree[rt].max;
        int mid=(tree[rt].l+tree[rt].r)>>1;
        if(r<=mid) return Query(lson,l,r);
        else if(l>mid) return Query(rson,l,r);
        else return max(Query(lson,l,r),Query(rson,l,r));//返回值是取函数返回最大值！！！
}//查询区间的时候不是max(t[lson].max,t[rson].max);！！！！！！！！！！

for(int i=n;i>=1;i--) 
{
        f[i]=min(f[i+a[i]+1],f[i+1]+1);//是要i当起点还是下一个点当起点
}

void add(int rt,int k)//建树和更新
{
        for(int i=rt;i<=n;i+=lowbit(i))
        {
	        c[i]+=k;
        }
}
int getsum(int rt)//区间求和
{
        int sum=0;
        for(int i=rt;i>=1;i-=lowbit(i))
        {
	        sum+=c[i];
        }        
        return sum;
}
//线段树代码还要长一些
void pushup(int rt)//回溯更新父节点 
{
        tree[rt].max=max(tree[lson].max,tree[rson].max);
}
void Build(int rt,int l,int r)//建树 
{
        tree[rt].l=l;
        tree[rt].r=r;
        if(l==r)
        {
	        tree[rt].max=a[l];
	        return;
        }
        int mid=(l+r)>>1;
        Build(lson,l,mid);
        Build(rson,mid+1,r);
        pushup(rt);
}
void Update(int rt,int pos,int val)//单点更新 
{
        if(tree[rt].l==tree[rt].r)
        {
	        tree[rt].sum+=val; 
	        return;
        }
        int mid=(tree[rt].l+tree[rt].r) >> 1;
        if(pos<=mid) Update(lson,pos,val);
        else Update(rson,pos,val);
        pushup(rt);
}
int Query(int rt,int l,int r)//查询区间和或者最大最小值都行改一下结构体后缀就行
{
        if(l<=tree[rt].l&&tree[rt].r<=r)
	        return tree[rt].max;
        int mid=(tree[rt].l+tree[rt].r)>>1;
        if(r<=mid) return Query(lson,l,r);
		else if(l>mid) return Query(rson,l,r);
		else return max(Query(lson,l,r),Query(rson,l,r));
}