前缀和

用于获取区间$[l,r]$间值得和

int a[N];
int s[N];
for(int i=1;i<=n;i++){
    s[i]=s[i-1]+a[i];
}
//[l,r]的值
cout<<s[r]-s[l-1];

二分

整数二分

使用STL在一个有序数组中返回下标

lower_bound(a,a+n,x)-a;
upper_bound(a,a+n,x)-a-1;

int sl(int l,int r,int x){
    while(l<r){//l与r为要找的东西的2个范围
        int mid=(l+r)/2;//取一个中间点
        if(a[mid]>=x){//if里面为check函数，写你想要的区间所达到的目的
            r=mid;//该区间在右边，则向左靠一下
        }else{
            l=mid+1;
        }
    }
    return l;
}
int sr(int l,int r,int x){
    while(l<r){
        int mid=(l+r+1)/2;
        if(a[mid]<=x){
            l=mid;
        }else{
            r=mid-1;//r减了，上面的r就要加
        }
    }
    return l;
}