poj 3468 A Simple Problem with Integers 線段樹成段延遲更新

用線段樹成段更新不能立即全部更新，必須搞延遲操作。其實，就是針對每個節點，另外搞一個域表示延遲
更新的數目。然後，在更新操作和查找操作的時候都把父親節點的延遲域往2個兒子走。
   這個題是要成段增加值，所以在寫PushDown函數的時候要注意，只能給兒子節點加上父親節點壓過來的值
乘以兒子區間的長度。這題貌似用樹狀數組也可以做，不過解法肯定意思不是那麼直白的。不過速度肯定會快。
   線段樹網上流行的解法都是開最多節點數目4倍的數組。以位置1作為根，每個位置其實代表的是一個區間。
某人位置1代表1-N或者0-(N-1)區間，具體看題目了。那麼2就代表區間1-(1+N)/2，3就代表區間(1+N)/2+1 - N了。
   至於lazy標記還是搞個大數組，意義和線段樹數組一樣，搞清楚之後寫起來都比較簡單，最重要的是變形來
解決一些要求奇怪的題目。

  
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef long long INT;

const INT MAX_N = 100010;
const INT INF = 0x7ffffffffffffffLL;
INT nTree[MAX_N << 2];
INT nAdd[MAX_N << 2];
INT nN, nQ;

void PushUp(INT nRt)
{
    nTree[nRt] = nTree[nRt << 1] + nTree[nRt << 1 | 1];
}

void BuildTree(INT nL, INT nR, INT nRt)
{
    nAdd[nRt] = 0;
    if (nL == nR)
    {
        scanf("%I64d", &nTree[nRt]);
        return;
    }
   
    INT nMid = (nL + nR) >> 1;
    BuildTree(nL, nMid, nRt << 1);
    BuildTree(nMid + 1, nR, nRt << 1 | 1);
    PushUp(nRt);
}

void PushDown(INT nL, INT nR, INT nRt)
{
    INT nMid = (nL + nR) >> 1;
    INT nLs = nRt << 1;
    INT nRs = nLs | 1;
   
    if (nAdd[nRt])
    {
        nAdd[nLs] += nAdd[nRt];
        nAdd[nRs] += nAdd[nRt];
        nTree[nLs] += (nMid - nL + 1) * nAdd[nRt];
        nTree[nRs] += (nR - nMid) * nAdd[nRt];
        nAdd[nRt] = 0;
    }
}

void Update(INT nL, INT nR, INT nRt, INT nX, INT nY, INT nV)
{
    if (nL >= nX && nR <= nY)
    {
        nTree[nRt] += nV * (nR - nL + 1);
        nAdd[nRt] += nV;
        return;
    }
   
    PushDown(nL, nR, nRt);
    INT nMid = (nL + nR) >> 1;
    if (nX <= nMid) Update(nL, nMid, nRt << 1, nX, nY, nV);
    if (nY > nMid) Update(nMid + 1, nR, nRt << 1 | 1, nX, nY, nV);
    PushUp(nRt);
}

INT Query(INT nL, INT nR, INT nRt, INT nX, INT nY)
{
    if (nL >= nX && nR <= nY)
    {
        return nTree[nRt];
    }
    PushDown(nL, nR, nRt);
    INT nAns = 0;
    INT nMid = (nL + nR) >> 1;
    if (nX <= nMid) nAns += Query(nL, nMid, nRt << 1, nX, nY);
    if (nY > nMid) nAns += Query(nMid + 1, nR, nRt << 1 | 1, nX, nY);
    return nAns;
}

int main()
{
    INT nTemp;
    while (scanf("%I64d%I64d", &nN, &nQ) == 2)
    {
        BuildTree(1, nN, 1);
       
        while (nQ--)
        {
            char szCmd[10];
            INT nX, nY, nV;
            scanf("%s", szCmd);
            if (szCmd[0] == 'Q')
            {
                scanf("%I64d%I64d", &nX, &nY);
                printf("%I64d\n", Query(1, nN, 1, nX, nY));
            }
            else
            {
                scanf("%I64d%I64d%I64d", &nX, &nY, &nV);
                Update(1, nN, 1, nX, nY, nV);
            }
        }
    }
   
    return 0;
}