循环求和

[题目链接](https://www.nowcoder.com/practice/f1725df80ee04cfebb6300f27c3d6464)

思路

牛牛把自然数序列里所有偶数加了负号，变成 $1, -2, 3, -4, 5, -6, \ldots$ 给定区间 $[L, R]$ ，要求这段数的和。

找前缀和的规律

先不急着算区间和，想一想前缀和 $S(n) = a_1 + a_2 + \cdots + a_n$ 长什么样。把前几项列出来：

$ $S(1) = 1,\quad S(2) = 1-2 = -1,\quad S(3) = -1+3 = 2,\quad S(4) = 2-4 = -2$ $

$ $S(5) = -2+5 = 3,\quad S(6) = 3-6 = -3$ $

规律很明显了：

当 $n$ 是奇数时， $S(n) = \dfrac{n+1}{2}$ ；
当 $n$ 是偶数时， $S(n) = -\dfrac{n}{2}$ 。

为什么呢？偶数个数可以两两配对 $(1,-2),(3,-4),\ldots$ ，每一对的和都是 $-1$ ，共 $n/2$ 对，所以 $S(n) = -n/2$ 。奇数就是在偶数基础上再加一个正数 $n$ ，即 $S(n) = -(n-1)/2 + n = (n+1)/2$ 。

区间和

有了前缀和公式， $[L, R]$ 的答案就是 $S(R) - S(L-1)$ ， $O(1)$ 搞定。

注意 $L=1$ 时 $S(0) = 0$ ，在代码里要处理一下边界。

代码

C++
Java
Python3
JavaScript

#include <bits/stdc++.h>
using namespace std;
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        long long l,r;
        scanf("%lld%lld",&l,&r);
        auto S = [](long long n) -> long long {
            if(n <= 0) return 0;
            if(n % 2 == 0) return -n / 2;
            else return (n + 1) / 2;
        };
        printf("%lld\n", S(r) - S(l - 1));
    }
    return 0;
}

import java.util.Scanner;
import java.io.*;

public class Main {
    static long S(long n) {
        if (n <= 0) return 0;
        if (n % 2 == 0) return -n / 2;
        else return (n + 1) / 2;
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();
        while (t-- > 0) {
            String[] parts = br.readLine().trim().split("\\s+");
            long l = Long.parseLong(parts[0]);
            long r = Long.parseLong(parts[1]);
            sb.append(S(r) - S(l - 1)).append('\n');
        }
        System.out.print(sb);
    }
}

import sys
input = sys.stdin.readline

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

t = int(input())
out = []
for _ in range(t):
    l, r = map(int, input().split())
    out.append(str(S(r) - S(l - 1)))
print('\n'.join(out))

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    let idx = 0;
    const t = parseInt(lines[idx++]);
    const res = [];
    function S(n) {
        if (n <= 0n) return 0n;
        if (n % 2n === 0n) return -n / 2n;
        else return (n + 1n) / 2n;
    }
    for (let i = 0; i < t; i++) {
        const parts = lines[idx++].split(/\s+/);
        const l = BigInt(parts[0]);
        const r = BigInt(parts[1]);
        res.push((S(r) - S(l - 1n)).toString());
    }
    console.log(res.join('\n'));
});

复杂度分析

时间复杂度： $O(T)$ ，每组查询 $O(1)$ 计算。
空间复杂度： $O(1)$ （不计输入输出缓冲）。