懒更新|单点查询

lc1636

带懒标记的区间加法、乘法、单点查询的实现

全局 add、mul 懒标记代替逐个修改元素，append 时用费马小定理求逆元还原原值

查询时 O(1) 计算真实值

时间复杂度全操作 O(logMOD)

class Fancy {
static constexpr int MOD = 1'000'000'007;

vector<int> vals;
long long add = 0;
long long mul = 1;

long long pow(long long x, int n) {
long long res = 1;
for (; n; n /= 2) {
if (n % 2) {
res = res * x % MOD;
}
x = x * x % MOD;
}
return res;
}

public:
void append(int val) {
// 注意这里有减法，计算结果可能是负数，+MOD 可以保证计算结果非负
vals.push_back((val - add + MOD) * pow(mul, MOD - 2) % MOD);
}

void addAll(int inc) {
add = (add + inc) % MOD;
}

void multAll(int m) {
mul = mul * m % MOD;
add = add * m % MOD;
}

int getIndex(int idx) {
if (idx >= vals.size()) {
return -1;
}
return (vals[idx] * mul + add) % MOD;
}
};