글 읽기 - 구간합 구하기 펜윅 트리 시간초과 질문합니다..!

kyaryunha 6년 전 0

예시 데이터로는 잘 되는데,

제출하니 시간초과가 납니다..!

혹시 왜 시간초과가 나는지 알려주실 분 계실까요?

#include<stdio.h>
#include<vector>
typedef long long ll;
using namespace std;
ll n,m,k,a,b,c,d;
ll num,dap;
ll sum(vector<ll>& tree, int i)
{
    ll res=0;
    while(i>0)
    {
        res+=tree[i];
        i-=(i&-i);
    }
    return res;
}
void update(vector<ll>& tree, int i, ll diff)
{
    while(i<tree.size())
    {
        tree[i]+=diff;
        i+=(i&-i);
    }
}
int main(void)
{
    scanf("%lld %lld %lld",&n,&m,&k);
    vector<ll> tree(n+1);
    k+=m;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&num);
        update(tree,i,num);
    }
    for(;k>0;k--)
    {
        scanf("%lld",&a);
        if(a==1)
        {
            scanf("%lld %lld %lld",&b,&c,&d);
            for(int i=b;i<=c;i++)
                update(tree,i,d);
        }
        else
        {
            scanf("%lld %lld",&b,&c);
            dap=sum(tree,c)-sum(tree,b-1);
            printf("%lld\n",dap);
        }
    }
}