当前位置：首页 > article >正文

acwing算法基础02一高精度,前缀和，差分

article 2024/11/14 17:53:02

在这里插入图片描述

#include <iostream>
#include <vector>
using namespace std;

const int N = 1e6 + 10;
//模板 C=A+B

vector<int> add(vector<int> &A,vector <int> &B)
{
     vector<int> C;
    int t = 0;  // 用来保存每位的和（包括进位）
       // 计算加法直到所有位都处理完
    for(int i=0;i<A.size()||i<B.size();i++)
    {
         if(i<A.size()) t+=A[i];
         if(i<B.size()) t+=B[i];
         //t 里存的 是a[i]+b[i]+上一位进位
         C.push_back(t%10);// 当前位的结果
         t /= 10;//进位
         
    }
    if(t)C.push_back(1);
    return C;
}
int main()
{
    string a,b;//  太长要用string
    vector<int> A,B;//vector自带size 用vecor存储
    cin>>a>>b;//a="123456"a是string类 所以要把a每一个数抠出来放到vector中
    for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');//存的是数字 减去一个偏移量 A={6,5,4,3,2,1
    for(int i= b.size()-1;i>=0;i--) B.push_back(b[i]-'0');//存的是数字 减去一个偏移量 
   vector<int> C = add(A, B);// 调用 add 函数得到结果 C
    for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
}

在这里插入图片描述
sr：前i个数的和
sl-1 前l-1 个数的和

把s0 定成0 以1为前缀和

#include<iostream>

using namespace std;

const int N =100010;

int n,m;
int a[N],s[N];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
       // 计算前缀和 s
    for(int i=1;i<=n;i++){
        s[i]=s[i-1]+a[i];
    }
    while(m--){
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d\n",s[r]-s[l-1] );//得出来l到r的范围
    }
    return 0;
}