题解 | #循环求和#

题目链接

循环求和

题目描述

牛牛定义了一个新的自然数序列： $1, -2, 3, -4, 5, \dots$ 。

即，对于一个自然数 $n$ ，如果它是奇数，其值为 $n$ ；如果它是偶数，其值为 $-n$ 。

现在需要计算这个序列第 $L$ 项到第 $R$ 项之间的和。

解题思路

这是一个求解特殊序列区间和的问题。由于区间的左右端点 $L$ 和 $R$ 的值可能非常大（可达 $10^9$ ），直接循环累加会导致超时。因此，我们需要寻找一种更高效的数学方法，通常是利用前缀和的思想。

1. 前缀和

区间 $[L, R]$ 的和可以表示为 (从第 1 项到第 R 项的和) - (从第 1 项到第 L-1 项的和)。

如果我们能用一个公式 $S(n)$ 快速计算出序列前 $n$ 项的和，那么问题就迎刃而解了。答案就是 $S(R) - S(L-1)$ 。

2. 推导前缀和公式 $S(n)$

我们来观察一下前缀和 $S(n) = \sum_{i=1}^{n} (-1)^{i+1} \cdot i$ 的规律：

$S(1) = 1$

$S(2) = 1 - 2 = -1$

$S(3) = 1 - 2 + 3 = 2$

$S(4) = 1 - 2 + 3 - 4 = -2$

$S(5) = S(4) + 5 = 3$

$S(6) = S(5) - 6 = -3$

可以发现一个非常清晰的模式：

当 $n$ 是奇数时， $S(n) = (n+1)/2$ 。
当 $n$ 是偶数时， $S(n) = -n/2$ 。

这个公式可以通过将序列中的数两两配对来证明，例如 $(1-2) + (3-4) + \dots$ ，每一对的和都是 $-1$ 。

3. 最终算法

根据推导出的公式，我们可以设计一个函数 get_s(n)，在 $\mathcal{O}(1)$ 的时间内计算出前 $n$ 项的和。

对于每个查询 $(L, R)$ ，我们只需计算 $get_s(R) - get_s(L-1)$ 即可得到答案。

注意，输入的 $L$ 和 $R$ 很大，计算过程中应使用 64 位整型（如 C++ 的 long long）以避免溢出。

代码

c++
java
python

#include <bits/stdc++.h>

using namespace std;

long long get_s(long long n) {
    if (n == 0) {
        return 0;
    }
    if (n % 2 == 1) {
        return (n + 1) / 2;
    } else {
        return -n / 2;
    }
}

void solve() {
    long long l, r;
    cin >> l >> r;
    long long ans = get_s(r) - get_s(l - 1);
    cout << ans << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            solve(sc);
        }
    }

    public static long getS(long n) {
        if (n == 0) {
            return 0;
        }
        if (n % 2 == 1) {
            return (n + 1) / 2;
        } else {
            return -n / 2;
        }
    }
    
    public static void solve(Scanner sc) {
        long l = sc.nextLong();
        long r = sc.nextLong();
        long ans = getS(r) - getS(l - 1);
        System.out.println(ans);
    }
}

import sys

def get_s(n):
    if n == 0:
        return 0
    if n % 2 == 1:
        return (n + 1) // 2
    else:
        return -n // 2

def solve():
    l, r = map(int, sys.stdin.readline().split())
    ans = get_s(r) - get_s(l - 1)
    print(ans)

def main():
    try:
        t_str = sys.stdin.readline()
        if not t_str: return
        t = int(t_str)
        for _ in range(t):
            solve()
    except (IOError, ValueError):
        return

if __name__ == "__main__":
    main()

算法及复杂度

算法：数学 / 前缀和
时间复杂度：对于 $T$ 组测试数据，每次查询的时间复杂度是 $\mathcal{O}(1)$ ，所以总时间复杂度为 $\mathcal{O}(T)$ 。
空间复杂度： $\mathcal{O}(1)$ 。