Tổng phần tử từ chỉ số L đến R trong mảng arr[i] = i*(-1)^i trong C++

Cho L, R và mảng arr[i] = i * (-1)^i. Tính tổng các phần tử từ chỉ số L đến R.

Ví dụ

Đầu vào: L = 2, R = 6

Đầu ra: 4

Giải thích: arr = {-1, 2, -3, 4, -5, 6}. Tổng từ 2 đến 6: 2 + (-3) + 4 + (-5) + 6 = 4

Phương pháp 1: Lặp O(N)

int tinhTong(int L, int R) {
    int tong = 0;
    for (int i = L; i <= R; i++)
        tong += i * pow(-1, i);
    return tong;
}

Phương pháp 2: Công thức toán học O(1)

Tổng n số chẵn đầu: n*(n+1)

Tổng n số lẻ đầu: n*n

Số chẵn ≤ n: n/2, số lẻ ≤ n: (n+1)/2

Tổng = [Tổng chẵn đến R - Tổng chẵn đến L-1] - [Tổng lẻ đến R - Tổng lẻ đến L-1]

long tongChanLe(int n, bool laChan) {
    long k = laChan ? n/2 : (n+1)/2;
    return laChan ? k*(k+1) : k*k;
}

int tinhTongNhanh(int L, int R) {
    return (tongChanLe(R, true) - tongChanLe(L-1, true)) 
         - (tongChanLe(R, false) - tongChanLe(L-1, false));
}

Ví dụ mã nguồn

#include <iostream>
using namespace std;

long tongChanLe(int n, bool laChan) {
    long k = laChan ? n/2 : (n+1)/2;
    return laChan ? k*(k+1) : k*k;
}

int tinhTong(int L, int R) {
    return (tongChanLe(R, true) - tongChanLe(L-1, true))
         - (tongChanLe(R, false) - tongChanLe(L-1, false));
}

int main() {
    int L = 3, R = 15;
    cout << "Tổng từ " << L << " đến " << R << " = " << tinhTong(L, R);
    return 0;
}

Kết quả

Tổng từ 3 đến 15 = -9