#include "data_structure/binary_indexed_tree.hpp"
#pragma once #include<vector> /** * @brief BinaryIndexedTree */ struct BIT{ std::vector<long long> bit; int n; BIT(long long n):n(n){ bit.resize(n+1,0); } //0-indexed [0,x)-sum long long sum(long long x){ long long res=0; for(int i=x;i;i-=i&-i)res+=bit[i]; return res; } //0-indexed [x,y)-sum long long sum(long long x,long long y){ return sum(y)-sum(x); } //0-indexed void add(long long x,long long val){ if(x>=n)return; for(long long i=x+1;i<=n;i+=i&-i)bit[i]+=val; } };
#line 2 "data_structure/binary_indexed_tree.hpp" #include<vector> /** * @brief BinaryIndexedTree */ struct BIT{ std::vector<long long> bit; int n; BIT(long long n):n(n){ bit.resize(n+1,0); } //0-indexed [0,x)-sum long long sum(long long x){ long long res=0; for(int i=x;i;i-=i&-i)res+=bit[i]; return res; } //0-indexed [x,y)-sum long long sum(long long x,long long y){ return sum(y)-sum(x); } //0-indexed void add(long long x,long long val){ if(x>=n)return; for(long long i=x+1;i<=n;i+=i&-i)bit[i]+=val; } };