HDU 1166 線段樹的區間查詢和單點更新

之前在學習線段樹，怎麼看都不懂，但是每次看都能明白那麼一點，後來看了一片部落格，一位大神的随筆，看了一個上午終于了解了線段樹

po出部落格位址，剛入門的同學可以好好看一看，會有一些收獲https://www.cnblogs.com/TheRoadToTheGold/p/6254255.html

這道題标準的模版題，單點更新，并不涉及lazy操作。

# include <iostream>
# include <string>
using namespace std;
const int N=5*1e5+5;
int ans=0;
struct node
{
    int left,right;
    int val;
    int lazy;
    int mid()
    { 
        return (left+right)/2; 
    }
} tree[4*N];
inline void build(int rt,int l,int r)
{
    tree[rt].left=l;
    tree[rt].right=r;
    if(l==r)
    {
        std::ios::sync_with_stdio(false);
        cin>>tree[rt].val;
        return ;
    }
    build(rt<<1,l,(l+r)/2);
    build(rt<<1|1,(l+r)/2+1,r);
    tree[rt].val=tree[rt<<1].val + tree[rt<<1|1].val;
}
inline void push_down(int rt)
{
    tree[rt<<1].lazy+=tree[rt].lazy;
    tree[rt<<1|1].lazy+=tree[rt].lazy;
    tree[rt<<1].val+=tree[rt].lazy*(tree[rt<<1].right - tree[rt<<1].left +1);
    tree[rt<<1|1].val+=tree[rt].lazy*(tree[rt<<1|1].right - tree[rt<<1|1].right +1);
    tree[rt].lazy=0;
}

inline void update(int rt,int pos,int num)
{
    if(tree[rt].left == tree[rt].right)
    {
    //    tree[rt].lazy+=num;
        tree[rt].val+=num;
        return ;
    }
///    if(tree[rt].lazy)
//    push_down(rt);
    int mid=tree[rt].mid();
    if(pos<=mid)
    update(rt<<1,pos,num);
    else
    update(rt<<1|1,pos,num);
    tree[rt].val=tree[rt<<1].val + tree[rt<<1|1].val;
}

inline void query(int rt,int x,int y) 
{
    if(tree[rt].left>=x && tree[rt].right<=y)
    {
        ans+=tree[rt].val;
        return ;
    }
//    if(tree[rt].lazy)
//    push_down(rt);
    int mid=tree[rt].mid();
    if(x<=mid)
    query(rt<<1,x,y);
    if(y>mid)
    query(rt<<1|1,x,y);
}
int main()
{
    int t;
    std::ios::sync_with_stdio(false);
    cin>>t;
    string str;
    for(int k=1;k<=t;k++)
    {
        int n;
        cin>>n;
        int x,y;
        build(1,1,n);
        cout<<"Case "<<k<<":"<<endl;
        while(cin>>str)
        {
            if(str[0]=='E')
            break;
            else
            {
            cin>>x>>y;
            if(str[0]=='Q')
            {
                ans=0;
                query(1,x,y);
                cout<<ans<<endl;
            }
            else
            if(str[0]=='A')
            {
                
                update(1,x,y);
            }
            else
            {
                update(1,x,-y);
            }
            }
        }
    }
    return 0;
}
其實這道題卡在時間上了，不建議寫我這種update函數，畢竟隻是單點更新，可以設定一個數組記錄每個葉子節點的位置，直接自底向上的更新會更節省時間，
而這種自頂向下的更新更适合區間更新(+lazy操作)。      

轉載于:https://www.cnblogs.com/ss1398736/p/9605650.html