Fenwick Tree

펜윅 트리로 할 수 있는 것:

 

- 점 업데이트, 구간 쿼리

 

2042번: 구간 합 구하기

 

#include<bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
typedef long long ll;
struct Fenwick {
    vector<ll> tree; int n;
    Fenwick(int n) : tree(n+1), n(n) {}
    void init() {
        for(int i=1;i<=n;i++){
            int j=i+(i&-i);
            if(j<=n) tree[j]+=tree[i];
        }
    }
    void update(int i,ll val) {
        for(;i<=n;i+=i&-i) tree[i]+=val;
    }
    ll query(int i) {
        ll res=0;
        for(;i;i-=i&-i) res+=tree[i];
        return res;
    }
};
int main()
{
    fastio;
    int n,m,k;
    cin >> n >> m >> k;
    Fenwick fen(n);
    for(int i=1;i<=n;i++) cin >> fen.tree[i];
    fen.init();
    for(m+=k;m--;){
        int t; cin >> t;
        if(t==1){
            int i; ll val;
            cin >> i >> val;
            fen.update(i,val-(fen.query(i)-fen.query(i-1)));
        }
        else{
            int l,r;
            cin >> l >> r;
            cout << fen.query(r)-fen.query(l-1) << '\n';
        }
    }
}

 

 

- 구간 업데이트, 점 쿼리

 

16975번: 수열과 쿼리 21

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5;
int n,m;
ll fen[N+1],a[N+1];
void build()
{
    for(int i=1;i<=n;i++){
        int j=i+(i&-i);
        if(j<=n) fen[j]+=fen[i];
    }
}
void update(int i,ll val)
{
    for(;i<=n;i+=i&-i) fen[i]+=val;
}
ll query(int i)
{
    ll res=0;
    for(;i;i-=i&-i) res+=fen[i];
    return res;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        fen[i]=a[i]-a[i-1];
    }
    build();
    for(scanf("%d",&m);m--;){
        int t;
        scanf("%d",&t);
        if(t==1){
            int i,j; ll k;
            scanf("%d%d%lld",&i,&j,&k);
            update(i,k);
            if(j<n) update(j+1,-k);
        }
        else{
            int x;
            scanf("%d",&x);
            printf("%lld\n",query(x));
        }
    }
}

 

 

- 구간 업데이트, 구간 쿼리

 

10999번: 구간 합 구하기 2

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6;
int n,m,k;
ll a[N+1],b[N+1];
void rngupdate(int i,ll mul,ll add)
{
    for(;i<=n;i+=i&-i) a[i]+=mul, b[i]+=add;
}
void update(int l,int r,ll val)
{
    rngupdate(l,val,-val*(l-1));
    rngupdate(r,-val,val*r);
}
ll query(int i)
{
    ll mul=0,add=0;
    for(int i1=i;i1;i1-=i1&-i1) mul+=a[i1], add+=b[i1];
    return mul*i+add;
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++){
        ll x;
        scanf("%lld",&x);
        update(i,i,x);
    }
    for(m+=k;m--;){
        ll t,i,j,v;
        scanf("%lld%lld%lld",&t,&i,&j);
        if(t==1){
            scanf("%lld",&v);
            update(i,j,v);
        }
        else{
            printf("%lld\n",query(j)-query(i-1));
        }
    }
}

(build를 비슷하게 할 수 있지 않을까?)

 

 

(단, 역원?이 존재하는 연산들만 가능.)

(업데이트 예정.)