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

# Fenwick Tree

## Fenwick Tree

```cpp
template <typename T>
struct Fenwick { // 1-indexed
    T *data;
    int FMAX;
    void init(int N) { // Range: [1, N]
        FMAX = N;
        data = new T[FMAX + 2];
        memset(data, 0, sizeof(T) * (FMAX + 2));
    }
    void update(int idx, T v) {
        for(; idx <= FMAX; idx += idx & -idx) data[idx] += v;
    }
    T get(int idx) {
        T res = 0;
        for(; idx > 0; idx = idx & (idx - 1)) res += data[idx];
        return res;
    }
};

```

## Time Complexity

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