数据结构与算法-一维差分

条件：因为对差分求前缀和可以得到原数组，适用于区间修改。
题目：无
原理：无
代码：
#include 
#include 
#include   //sort
#include 
#include 
#include   //双端队列，头可插，尾可插
#include 
#include 
#include 
#include 
#include 
#include 
#include  //数值的限制范围
//(double)clock() / CLOCKS_PER_SEC <= 0.95 限制0.95s跑完
using namespace std;

class Solver {
    //通用属性
public:
    Solver() {
        //取消和c输出输入的同步，加快读取
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
    }

    //通用方法
public:
    void SaveCpp(string name) const {

        fstream input;
        fstream output;

        input.open("moota.cpp", ios::in);
        const string file = name + ".cpp";
        output.open(file.c_str(), ios::out);

        char c = 'O';
        while (!input.eof()) {
            input.get(c);
            output << c;
        }

        input.close();
        output.close();

    }

protected:
    //待实现方法
    virtual void BeginPlay() {
    };

    virtual void Playing() {
    };

    virtual void EndPlay() {
    };
public:
    //外观模式
    void Play() {
        BeginPlay();
        Playing();
        EndPlay();
    }
};
//差分和前缀和的关系
//差分的前缀和就是原数组
//前缀和的差分也是原数组
class SpecialSolver : public Solver {
public:
    typedef long long lld;
    static const lld MAX = static_cast(1e6);
    static const lld INF = static_cast(1e18);
private: //实例属性
    lld n, m;
private: //实例方法
    lld sub1D[MAX];
protected:
    virtual void BeginPlay() override {
        Solver::BeginPlay();
        cin >> n >> m;
        lld pre = 0, cur = 0;
        for (lld i = 1; i <= n; ++i) {
            cin >> cur;
            sub1D[i] = cur - pre;
            pre = cur;
        }
    };

    virtual void Playing() override {
        Solver::Playing();
        lld index;
        while (m--) {
            cin >> index;
            lld num = 0;
            for (lld i = 1; i <= index; ++i) {
                num += sub1D[i];
            }
            cout << num;
        }
    };

    virtual void EndPlay() override {
        Solver::EndPlay();

    };
};

SpecialSolver specialSolver;

int main() {
    //注意改名字
    //specialSolver.SaveCpp("一维差分模板");
    specialSolver.Play();
}
数据结构与算法-一维差分

C/C++/C#相关栏目本月热门文章
