程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Wikioi 1081 線段樹練習2

Wikioi 1081 線段樹練習2

編輯：C++入門知識

線段樹練習飄逸的寫法，自從自己改成這種寫法之後，線段樹就沒再練過，現在終於練得上了。

因為這裡查詢只是查詢了葉子結點，所以pushUp函數就用不上了，不過我沒去掉之前是3ms，去掉之後反而變成4ms了，搞不懂怎麼原因，沒用到，去掉之後應該更快才對啊，竟然變慢了，真搞不明白？

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define sc(a,b) scanf("%d%d",&a,&b)
#define pri(a) printf("%d\n",a)
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define MM 100004
#define MN 1008
#define INF 2000000000
#define eps 1e-8
using namespace std;
typedef long long ll;
typedef unsigned long long ULL;
int sum[MM],val[MM];
//void pushUp(int i)
//{
//    sum[i]=sum[i<<1]+sum[i<<1|1];
//}
void pushDown(int i) //處理lazy標記
{
    if(val[i])
    {
        val[i<<1]+=val[i],val[i<<1|1]+=val[i];
        sum[i<<1]+=val[i],sum[i<<1|1]+=val[i];
        val[i]=0;
    }
}
void build(int i,int l,int r)
{
    sum[i]=val[i]=0;
    if(l==r) return ;
    int mid=(l+r)>>1;
    build(lson),build(rson);
}
void update(int i,int l,int r,int L,int R,int v)
{
    if(L<=l&&r<=R)
    {
        val[i]+=v;
        sum[i]+=v;
        return ;
    }
    int mid=(l+r)>>1;
    pushDown(i);
    if(L<=mid) update(lson,L,R,v);
    if(R>mid) update(rson,L,R,v);
    //pushUp(i);
}
int query(int i,int l,int r,int x)
{
    if(l==x&&r==x) return sum[i];
    int mid=(l+r)>>1;
    pushDown(i);
    if(x<=mid) return query(lson,x);
    else return query(rson,x);
}
int main()
{
    int n,q,mm,i,a,b,s;
    sca(n);
    build(1,1,n);
    for(i=1;i<=n;i++)
    {
        sca(a);
        update(1,1,n,i,i,a);
    }
    sca(q);
    while(q--)
    {
        sca(mm);
        if(mm==1)
        {
            scanf("%d%d%d",&a,&b,&s);
            update(1,1,n,a,b,s);
        }
        else
        {
            sca(s);
            pri(query(1,1,n,s));
        }
    }
    return 0;
}