利用C++樹狀數(shù)組處理大規(guī)模數(shù)據(jù)

c++
小樊
83
2024-08-19 20:54:35
欄目: 編程語言

樹狀數(shù)組（Fenwick Tree）是一種用于高效處理動(dòng)態(tài)區(qū)間和的數(shù)據(jù)結(jié)構(gòu)，可以用來解決一些統(tǒng)計(jì)問題，比如求區(qū)間和、區(qū)間最大值、區(qū)間最小值等。在處理大規(guī)模數(shù)據(jù)時(shí)，樹狀數(shù)組可以幫助我們高效地進(jìn)行數(shù)據(jù)統(tǒng)計(jì)和查詢。

下面是一個(gè)使用C++實(shí)現(xiàn)樹狀數(shù)組的示例代碼：

#include <iostream>
#include <vector>

using namespace std;

// 樹狀數(shù)組的實(shí)現(xiàn)
class FenwickTree {
public:
    FenwickTree(int n) {
        tree.resize(n + 1, 0);
    }

    void update(int index, int delta) {
        while (index < tree.size()) {
            tree[index] += delta;
            index += index & -index;
        }
    }

    int query(int index) {
        int sum = 0;
        while (index > 0) {
            sum += tree[index];
            index -= index & -index;
        }
        return sum;
    }

private:
    vector<int> tree;
};

int main() {
    int n = 10; // 數(shù)據(jù)規(guī)模
    FenwickTree tree(n);

    // 更新元素
    tree.update(1, 2);
    tree.update(2, 3);
    tree.update(3, 5);

    // 查詢區(qū)間和
    cout << tree.query(3) << endl; // 輸出：10
    cout << tree.query(5) - tree.query(2) << endl; // 輸出：8

    return 0;
}

在上面的示例代碼中，我們實(shí)現(xiàn)了一個(gè)簡(jiǎn)單的樹狀數(shù)組類FenwickTree，并使用其來處理一些數(shù)據(jù)更新和求和操作。通過樹狀數(shù)組，我們可以高效地處理大規(guī)模數(shù)據(jù)，并快速進(jìn)行數(shù)據(jù)統(tǒng)計(jì)和查詢。

0 踩