用線段樹成段更新不能立即全部更新，必須搞延遲操作。其實(shí)，就是針對(duì)每個(gè)節(jié)點(diǎn)，另外搞一個(gè)域表示延遲
這個(gè)題是要成段增加值，所以在寫PushDown函數(shù)的時(shí)候要注意，只能給兒子節(jié)點(diǎn)加上父親節(jié)點(diǎn)壓過來的值
線段樹網(wǎng)上流行的解法都是開最多節(jié)點(diǎn)數(shù)目4倍的數(shù)組。以位置1作為根，每個(gè)位置其實(shí)代表的是一個(gè)區(qū)間。
#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;
}