---
id: "imported/ps/data-structure/tree/2d-fenwick"
title: "2D-Fenwick Tree"
description: "2D-Fenwick Tree 관련 기록."
kind: "record"
published: "2023-08-07T00:00:00.000Z"
tags: []
url: "https://www.readiz.com/notes/data-structure/tree/2d-fenwick/"
markdownUrl: "https://www.readiz.com/notes/data-structure/tree/2d-fenwick/index.md"
---

# 2D-Fenwick Tree

## 2D-Fenwick Tree

```cpp
template <typename T>
struct Fenwick2D { // 1-indexed
    vector<vector<T>> data;
    int N, M;
    void init(int N, int M) { // Row: N / Column: M
        this->N = N;
        this->M = M;
        data.resize(N + 2);
        for(int i = 0; i < N + 2; ++i) {
            data[i].resize(M + 2);
            fill(data[i].begin(), data[i].end(), 0);
        }
    }
    void update(int r, int c, T v) {
        for(int cr = r; cr <= N; cr += cr & -cr) {
            for(int cc = c; cc <= M; cc += cc & -cc) {
                data[cr][cc] += v;
            }
        }
    }
    T get(int r, int c) {
        T res = 0;
        for(int cr = r; cr > 0; cr -= cr & -cr) {
            for(int cc = c; cc > 0; cc -= cc & -cc) {
                res += data[cr][cc];
            }
        }
        return res;
    }
};

```

## Time Complexity

- Init: $O(NM)$
- Update: $O(\log N \times \log M)$
- Get: $O(\log N \times \log M)$