登录[Python3/Java/C++/Go/TypeScript] 一题一解：前缀和（清晰题解）
方法一：前缀和
根据题目描述，我们不妨假设把一个元素 $x$ 变为 $0$ 需要的最小操作次数为 $p$，那么 $p$ 是满足 $4^p \gt x$ 的最小整数。
我们知道了一个元素的最小操作次数，那么对于一个范围 $[l, r]$，我们假设 $[l, r]$ 范围内所有元素的最小操作次数之和为 $s$，最大操作次数为元素 $r$ 的操作次数 $mx$，那么 $[l, r]$ 范围内所有元素变为 $0$ 的最少操作次数为 $\max(\lceil s / 2 \rceil, mx)$。
我们定义一个函数 $f(x)$，表示范围 $[1, x]$ 内所有元素的最小操作次数之和，那么对于每个查询 $[l, r]$，我们可以计算出 $s = f(r) - f(l - 1)$ 和 $mx = f(r) - f(r - 1)$，从而得到答案。
###python
class Solution:
def minOperations(self, queries: List[List[int]]) -> int:
def f(x: int) -> int:
res = 0
p = i = 1
while p <= x:
cnt = min(p * 4 - 1, x) - p + 1
res += cnt * i
i += 1
p *= 4
return res
ans = 0
for l, r in queries:
s = f(r) - f(l - 1)
mx = f(r) - f(r - 1)
ans += max((s + 1) // 2, mx)
return ans
###java
class Solution {
public long minOperations(int[][] queries) {
long ans = 0;
for (int[] q : queries) {
int l = q[0], r = q[1];
long s = f(r) - f(l - 1);
long mx = f(r) - f(r - 1);
ans += Math.max((s + 1) / 2, mx);
}
return ans;
}
private long f(long x) {
long res = 0;
long p = 1;
int i = 1;
while (p <= x) {
long cnt = Math.min(p * 4 - 1, x) - p + 1;
res += cnt * i;
i++;
p *= 4;
}
return res;
}
}
###cpp
class Solution {
public:
long long minOperations(vector<vector<int>>& queries) {
auto f = [&](long long x) {
long long res = 0;
long long p = 1;
int i = 1;
while (p <= x) {
long long cnt = min(p * 4 - 1, x) - p + 1;
res += cnt * i;
i++;
p *= 4;
}
return res;
};
long long ans = 0;
for (auto& q : queries) {
int l = q[0], r = q[1];
long long s = f(r) - f(l - 1);
long long mx = f(r) - f(r - 1);
ans += max((s + 1) / 2, mx);
}
return ans;
}
};
###go
func minOperations(queries [][]int) (ans int64) {
f := func(x int64) (res int64) {
var p int64 = 1
i := int64(1)
for p <= x {
cnt := min(p*4-1, x) - p + 1
res += cnt * i
i++
p *= 4
}
return
}
for _, q := range queries {
l, r := int64(q[0]), int64(q[1])
s := f(r) - f(l-1)
mx := f(r) - f(r-1)
ans += max((s+1)/2, mx)
}
return
}
###ts
function minOperations(queries: number[][]): number {
const f = (x: number): number => {
let res = 0;
let p = 1;
let i = 1;
while (p <= x) {
const cnt = Math.min(p * 4 - 1, x) - p + 1;
res += cnt * i;
i++;
p *= 4;
}
return res;
};
let ans = 0;
for (const [l, r] of queries) {
const s = f(r) - f(l - 1);
const mx = f(r) - f(r - 1);
ans += Math.max(Math.ceil(s / 2), mx);
}
return ans;
}
###rust
impl Solution {
pub fn min_operations(queries: Vec<Vec<i32>>) -> i64 {
let f = |x: i64| -> i64 {
let mut res: i64 = 0;
let mut p: i64 = 1;
let mut i: i64 = 1;
while p <= x {
let cnt = std::cmp::min(p * 4 - 1, x) - p + 1;
res += cnt * i;
i += 1;
p *= 4;
}
res
};
let mut ans: i64 = 0;
for q in queries {
let l = q[0] as i64;
let r = q[1] as i64;
let s = f(r) - f(l - 1);
let mx = f(r) - f(r - 1);
ans += std::cmp::max((s + 1) / 2, mx);
}
ans
}
}
时间复杂度 $O(q \log M)$，其中 $q$ 是查询次数，而 $M$ 是查询范围的最大值。空间复杂度 $O(1)$。
有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~
