Khóa học CTDL và GT

#include <iostream>
#include <vector>

// Sử dụng 1-based indexing cho Fenwick Tree
class FenwickTree {
private:
    std::vector<long long> bit; // Mảng BIT
    int size; // Kích thước tối đa của mảng gốc (N)

public:
    // Khởi tạo BIT với kích thước N
    FenwickTree(int n) : size(n), bit(n + 1, 0) {}

    // Hàm cập nhật: Cộng delta vào phần tử tại index (1-based)
    void update(int index, long long delta) {
        // Đi lên cây, cập nhật các node chứa index
        for (; index <= size; index += index & -index) {
            bit[index] += delta;
        }
    }

    // Hàm truy vấn: Tính tổng tiền tố từ 1 đến index (1-based)
    long long query(int index) {
        long long sum = 0;
        // Đi xuống cây, tổng hợp các node cần thiết
        for (; index > 0; index -= index & -index) {
            sum += bit[index];
        }
        return sum;
    }

    // Hàm truy vấn tổng đoạn từ L đến R (1-based)
    long long query_range(int L, int R) {
        if (L > R) return 0;
        return query(R) - query(L - 1);
    }
};

int main() {
    int n; // Kích thước mảng gốc
    std::cout << "Nhap kich thuoc mang N: ";
    std::cin >> n;

    // Khởi tạo Fenwick Tree
    FenwickTree ft(n);

    // Giả sử mảng ban đầu toàn 0, sau đó có thể thêm các cập nhật ban đầu nếu cần
    // Ví dụ: Đọc mảng ban đầu và update vào BIT
    // std::cout << "Nhap N phan tu ban dau: ";
    // for (int i = 1; i <= n; ++i) {
    //     long long val;
    //     std::cin >> val;
    //     ft.update(i, val); // Update từng phan tu vao BIT
    // }

    int num_operations;
    std::cout << "Nhap so luong thao tac: ";
    std::cin >> num_operations;

    for (int i = 0; i < num_operations; ++i) {
        int type; // 1: update, 2: query
        std::cout << "Nhap loai thao tac (1: update, 2: query range): ";
        std::cin >> type;

        if (type == 1) {
            int index;
            long long delta; // Luong can cong/tru
            std::cout << "Nhap index (1-based) va luong thay doi delta: ";
            std::cin >> index >> delta;
            if (index >= 1 && index <= n) {
                ft.update(index, delta);
                std::cout << "Da cap nhat index " << index << " voi delta " << delta << std::endl;
            } else {
                 std::cout << "Index khong hop le!" << std::endl;
            }
        } else if (type == 2) {
            int L, R;
            std::cout << "Nhap doan [L, R] (1-based) de truy van tong: ";
            std::cin >> L >> R;
            if (L >= 1 && L <= R && R <= n) {
                 long long total_sum = ft.query_range(L, R);
                 std::cout << "Tong tren doan [" << L << ", " << R << "] la: " << total_sum << std::endl;
            } else {
                 std::cout << "Doan truy van khong hop le!" << std::endl;
            }
        } else {
            std::cout << "Loai thao tac khong hop le!" << std::endl;
        }
    }

    return 0;
}

#include <iostream>
#include <vector>

// Sử dụng 1-based indexing cho Fenwick Tree
class FenwickTree {
private:
    std::vector<long long> bit;
    int size;

public:
    FenwickTree(int n) : size(n), bit(n + 1, 0) {}

    void update(int index, long long delta) {
        for (; index <= size; index += index & -index) {
            bit[index] += delta;
        }
    }

    long long query(int index) {
        long long sum = 0;
        for (; index > 0; index -= index & -index) {
            sum += bit[index];
        }
        return sum;
    }

    // Không cần query_range cho bài này, chỉ query point.
};

int main() {
    int n; // Kích thước mảng gốc
    std::cout << "Nhap kich thuoc mang N: ";
    std::cin >> n;

    // Khởi tạo Fenwick Tree để quản lý mảng sai phân (difference array)
    // Mảng sai phân cũng có kích thước N, nhưng ta cần node R+1 cho cập nhật đoạn
    // nên kích thước BIT vẫn là N+1.
    FenwickTree ft_diff(n);

    // Mảng ban đầu coi như toàn 0 -> mảng sai phân ban đầu toàn 0

    int num_operations;
    std::cout << "Nhap so luong thao tac: ";
    std::cin >> num_operations;

    for (int i = 0; i < num_operations; ++i) {
        int type; // 1: update range, 2: query point
        std::cout << "Nhap loai thao tac (1: update range, 2: query point): ";
        std::cin >> type;

        if (type == 1) {
            int L, R;
            long long val; // Gia tri can cong them
            std::cout << "Nhap doan [L, R] (1-based) va gia tri v: ";
            std::cin >> L >> R >> val;
            if (L >= 1 && L <= R && R <= n) {
                // Cap nhat point L tren mang sai phan
                ft_diff.update(L, val);
                // Cap nhat point R+1 tren mang sai phan (neu R+1 <= N)
                if (R + 1 <= n) {
                    ft_diff.update(R + 1, -val);
                }
                 std::cout << "Da cap nhat doan [" << L << ", " << R << "] cong them " << val << std::endl;
            } else {
                 std::cout << "Doan cap nhat khong hop le!" << std::endl;
            }
        } else if (type == 2) {
            int index; // Index (1-based) can truy van
            std::cout << "Nhap index (1-based) can truy van gia tri: ";
            std::cin >> index;
            if (index >= 1 && index <= n) {
                 // Gia tri tai index chinh la tong tien to den index tren mang sai phan
                 long long value_at_index = ft_diff.query(index);
                 std::cout << "Gia tri tai index " << index << " la: " << value_at_index << std::endl;
            } else {
                 std::cout << "Index khong hop le!" << std::endl;
            }
        } else {
            std::cout << "Loai thao tac khong hop le!" << std::endl;
        }
    }

    return 0;
}

#include <iostream>
#include <vector>

// Sử dụng 1-based indexing cho Fenwick Tree
class FenwickTree {
private:
    std::vector<long long> bit;
    int size;

public:
    FenwickTree(int n) : size(n), bit(n + 1, 0) {}

    void update(int index, long long delta) {
        for (; index <= size; index += index & -index) {
            bit[index] += delta;
        }
    }

    long long query(int index) {
        long long sum = 0;
        for (; index > 0; index -= index & -index) {
            sum += bit[index];
        }
        return sum;
    }
};

int main() {
    int n; // Kích thước mảng gốc
    std::cout << "Nhap kich thuoc mang N: ";
    std::cin >> n;

    // Can 2 Fenwick Trees cho bai toan nay
    // ft1: Quan ly mang sai phan B (cap nhat delta vao B[L], B[R+1])
    // ft2: Quan ly mang sai phan B nhan voi chi so j (cap nhat delta*L vao B[L], delta*(R+1) vao B[R+1])
    FenwickTree ft1(n);
    FenwickTree ft2(n);

    int num_operations;
    std::cout << "Nhap so luong thao tac: ";
    std::cin >> num_operations;

    for (int i = 0; i < num_operations; ++i) {
        int type; // 1: update range, 2: query range
        std::cout << "Nhap loai thao tac (1: update range, 2: query range): ";
        std::cin >> type;

        if (type == 1) {
            int L, R;
            long long val; // Gia tri can cong them
            std::cout << "Nhap doan [L, R] (1-based) va gia tri v: ";
            std::cin >> L >> R >> val;
            if (L >= 1 && L <= R && R <= n) {
                // Cap nhat BIT1 (mang B)
                ft1.update(L, val);
                if (R + 1 <= n) {
                    ft1.update(R + 1, -val);
                }

                // Cap nhat BIT2 (mang j*B[j])
                ft2.update(L, val * (L - 1)); // Tại L: delta * (L-1)
                if (R + 1 <= n) {
                    ft2.update(R + 1, -val * R); // Tại R+1: -(delta * R)
                }
                 std::cout << "Da cap nhat doan [" << L << ", " << R << "] cong them " << val << std::endl;
            } else {
                 std::cout << "Doan cap nhat khong hop le!" << std::endl;
            }
        } else if (type == 2) {
            int L, R; // Doan can truy van
            std::cout << "Nhap doan [L, R] (1-based) de truy van tong: ";
            std::cin >> L >> R;
            if (L >= 1 && L <= R && R <= n) {
                 // Ham tinh tong tien to cua mang goc A den k
                 auto query_prefix_sum_A = [&](int k) {
                     if (k <= 0) return 0LL;
                     // Sum[1..k] = k * sum(B[1..k]) - sum(j*B[j] for j=1..k)
                     // Cong thuc chinh xac hon voi 1-based indexing cua BIT:
                     // Sum[1..k] = (k) * BIT1.query(k) - BIT2.query(k)
                     // (Xem giai thich chi tiet hon o phan phan tich, do cong thuc co the bien doi tuy phep nhan chi so)
                     // Quay lai cong thuc tong quat: PrefixSumA[k] = sum_{j=1 to k} A[j] = sum_{j=1 to k} (sum_{i=1 to j} B[i])
                     // = sum_{i=1 to k} B[i] * (so luong j >= i)
                     // = sum_{i=1 to k} B[i] * (k - i + 1)
                     // = sum_{i=1 to k} B[i]*(k+1) - sum_{i=1 to k} B[i]*i
                     // = (k+1) * sum(B[1..k]) - sum(i*B[i] for i=1..k)

                     // Tuy nhien, cach cap nhat BIT2 cua chung ta la val*(L-1) va -val*R
                     // Nen tong tien to den k la: k*sum(B[1..k]) - sum(i*B[i] for i=1..k) + sum_from_update_L (val*(L-1)) + sum_from_update_R+1 (-val*R)
                     // Tong tien to cua A den k (PrefixSumA[k]) sau khi update (L, R, val)
                     // = tong cac val * (so lan val anh huong den A[i] voi i <= k)
                     // Mot cap nhat (L, R, val) anh huong den A[i] them val voi moi i thuoc [L, min(R, k)]. Co min(R, k) - L + 1 phan tu.
                     // Sum A[1..k] = sum (tong cac cap nhat toi A[i]) voi i tu 1 toi k
                     // = sum_over_updates (val * do dai doan giao [L_u, R_u] va [1, k])
                     // Day la cach nghi phuc tap. Hay dung lai cong thuc mảng sai phan:
                     // A[i] = sum(B[1..i])
                     // Sum(A[L..R]) = Sum(A[1..R]) - Sum(A[1..L-1])
                     // Sum(A[1..k]) = sum_{i=1..k} A[i] = sum_{i=1..k} (sum_{j=1..i} B[j])
                     // = sum_{j=1..k} B[j] * (k-j+1)
                     // = (k+1)*sum_{j=1..k} B[j] - sum_{j=1..k} j*B[j]
                     // BIT1.query(k) = sum_{j=1..k} B[j]
                     // BIT2.query(k) = sum_{j=1..k} j*B[j] (do cach chung ta update BIT2: update(idx, val*idx))
                     // Wait, cai dat o tren update(L, val*(L-1)) va update(R+1, -val*R)
                     // Khi update L, R voi val, ta them +val vao B[L] va -val vao B[R+1]
                     // A[i] = sum_{j=1..i} B[j]
                     // Sum A[1..k] = sum_{i=1..k} A[i] = sum_{i=1..k} sum_{j=1..i} B[j]
                     // = sum_{j=1..k} B[j] * (k-j+1)
                     // = (k+1) * sum_{j=1..k} B[j] - sum_{j=1..k} j*B[j]
                     // Ta can 2 BIT:
                     // BIT1: luu B[j] -> query(k) cho ra sum_{j=1..k} B[j]
                     // BIT2: luu j*B[j] -> query(k) cho ra sum_{j=1..k} j*B[j]
                     // Update (L, R, val):
                     // B[L] += val, B[R+1] -= val
                     // BIT1.update(L, val), BIT1.update(R+1, -val)
                     // j*B[j] update:
                     // L*B[L] += L*val
                     // (R+1)*B[R+1] -= (R+1)*val
                     // BIT2.update(L, L*val), BIT2.update(R+1, -(R+1)*val)
                     // Công thức truy vấn tổng tiền tố Sum(A[1..k]) = (k+1)*BIT1.query(k) - BIT2.query(k) là đúng với cách update này.

                     long long sum_B = ft1.query(k); // sum_{j=1..k} B[j]
                     long long sum_jB = ft2.query(k); // sum_{j=1..k} j*B[j]
                     return (long long)(k + 1) * sum_B - sum_jB;
                 };

                 long long total_sum = query_prefix_sum_A(R) - query_prefix_sum_A(L - 1);
                 std::cout << "Tong tren doan [" << L << ", " << R << "] la: " << total_sum << std::endl;
            } else {
                 std::cout << "Doan truy van khong hop le!" << std::endl;
            }
        } else {
            std::cout << "Loai thao tac khong hop le!" << std::endl;
        }
    }

    return 0;
}