二分答案
基本code
int Find(int l,int r)
{
int ans,mid;
while(l<=r)
{
int mid=l+r>>1;
if(Check(mid)) ans=mid,r=mid-1;//舍弃右半部分
else l=mid+1;//舍弃左半部分
}
return ans;
}
前缀和
基本code
#inlcude<bits/stdc++.h>
using namespace std;
int sum[100],a[100];
int _n;//基本个数
int main()
{
for(int i=1;i<=_n;i++)
cin>>a[i],sum[i]=sum[i-1]+a[i];
ask_sum(l,r)=sum[r]-sum[l-1];//ask
//一维公式
for(int i=1;i<=_n;i++)
for(int j=1;j<=_n;j++)
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];//build
for(int a0=1;a0<=_n;a0++)
for(int b0=1;b0<=_n;b0++)
for(int a1=a0;a1<=_n;a1++)
for(int b1=b0;b1<=_n;b1++)
{
ask_sum([a0,b0],[a1,b1])=sum[a1][b1]-sum[a0-1][b1]-sum[a1][b0-1]+sum[a0-1][b0-1];
}//ask
return 0;
}
差分
基本code
d[]=>差分数列
for(int i=1;i<=_n;i++)
{
cin>>a[i];
d[i]=a[i]-a[i-1];
}
统治区域值(l,r)+d
d[l]+d;
d[r+1]-d;
for(int i=1;i<=_n;i++)
sum[i]=sum[i-1]+a[i];//还原