BIT (Binary Indexed Tree)
(structure/bit.hpp)

• View this file on GitHub
• Last update: 2022-08-03 17:09:04+09:00
• Include: #include "structure/bit.hpp"

概要

• 1-indexにして閉区間で考える

実装のヒント

• (ind & -ind) で最後の区間を求めて足し引きをする。
• 足し算は木の親をたどる。
• 引き算は深さ優先探索の帰りがけ順の前の区間に移動する。

参考

• スライド
• かつっぱEDPC Q

Verified with

• test/structure/BIT.aoj_DSL_2_B.test.cpp

Code

#pragma once
#include <vector>


template <typename T>
struct BIT {
    int N;
    std::vector<T> bit;
    BIT(size_t sz) : N(sz + 2), bit(N, 0) {}

    void add(int i, T x){
        for(int idx = i; idx <= N; idx += idx & -idx){
            bit[idx] += x;
        }
    }

    T sum(int i){
        T ret = 0;
        for(int idx = i; idx > 0; idx -= idx & -idx){
            ret += bit[idx];
        }
        return ret;
    }
};

#line 2 "structure/bit.hpp"
#include <vector>


template <typename T>
struct BIT {
    int N;
    std::vector<T> bit;
    BIT(size_t sz) : N(sz + 2), bit(N, 0) {}

    void add(int i, T x){
        for(int idx = i; idx <= N; idx += idx & -idx){
            bit[idx] += x;
        }
    }

    T sum(int i){
        T ret = 0;
        for(int idx = i; idx > 0; idx -= idx & -idx){
            ret += bit[idx];
        }
        return ret;
    }
};

Back to top page