這是一個線段樹的經典應用問題，要求維護一個序列，支持對某個區間RMQ（查詢區間最值），支持修改一個區間，使區間中所有數增加某個數值。

在線段樹中修改某個區間的值，爲保證高效，要使用標記向下傳。

下面是楊弋在NOI2008冬令營上的講稿。

線段樹講稿

這是swq大牛的題解。

/*
 * Problem: 售票系統
 * Author: Guo Jiabao
 * Time: 2009.3.20 20:51
 * State: Solved
 * Memo: 線段樹修改區間 優化
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=60001;
using namespace std;
struct sgt_node
{
    sgt_node *left,*right;
    int a,b,m,v,add;
};
int N,LIM,Q,SS=-1;
sgt_node *sgt_root,SE[MAXN*2];
inline sgt_node* sgt_new(int a,int b)
{
    SE[++SS].m=(a+b)/2;
    SE[SS].a=a;SE[SS].b=b;
    SE[SS].add=SE[SS].v=0;
    SE[SS].left=SE[SS].right=0;
    return &SE[SS];
}
void sgt_create(sgt_node *&p,int a,int b)
{
    p=sgt_new(a,b);
    if (a!=b)
    {
        sgt_create(p->left,a,p->m);
        sgt_create(p->right,p->m+1,b);
    }
}
void sgt_movedown(sgt_node *p)
{
    p->v+=p->add;
    if (p->a!=p->b)
    {
        p->left->add+=p->add;
        p->right->add+=p->add;
    }
    p->add=0;
}
void sgt_edit(sgt_node *p,int a,int b,int delta)
{
    if (p->a==a && p->b==b)
    {
        p->add+=delta;
        sgt_movedown(p);
    }
    else
    {
        sgt_movedown(p->left);
        sgt_movedown(p->right);
        if (b<=p->m)
            sgt_edit(p->left,a,b,delta);
        else if (a>=p->m+1)
            sgt_edit(p->right,a,b,delta);
        else
        {
            sgt_edit(p->left,a,p->m,delta);
            sgt_edit(p->right,p->m+1,b,delta);
        }
        p->v=(p->left->v > p->right->v)?p->left->v:p->right->v;
    }
}
bool sgt_find(sgt_node *p,int a,int b,int delta)
{
    if (p->add)
        sgt_movedown(p);
    if (p->a==a && p->b==b)
        return p->v+delta<=LIM;
    if (b<=p->m)
        return sgt_find(p->left,a,b,delta);
    if (a>=p->m+1)
        return sgt_find(p->right,a,b,delta);
    if (!sgt_find(p->left,a,p->m,delta))
        return false;
    else
        return sgt_find(p->right,p->m+1,b,delta);
}
void init()
{
    freopen("railway.in","r",stdin);
    freopen("railway.out","w",stdout);
    scanf("%d%d%d",&N,&LIM,&Q);
    sgt_create(sgt_root,1,N);
}
void solve()
{
    int i,a,b,c;
    for (i=1;i<=Q;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        b--;
        if (sgt_find(sgt_root,a,b,c))
        {
            sgt_edit(sgt_root,a,b,c);
            printf("YES\n");
        }
        else
            printf("NO\n");
    }
}
int main()
{
    init();
    solve();
    return 0;
}

<div class="MainText">

<strong>【問題描述】</strong>
某次列車途經C個城市，城市編號依次爲1到C，列車上共有S個座位，鐵路局規定售出的車票只能是坐票， 即車上所有的旅客都有座。售票系統是由計算機執行的，每一個售票申請包含三個參數，分別用O、D、N表示，O爲起始站，D爲目的地站，N爲車票張數。售票 系統對該售票申請作出受理或不受理的決定，只有在從O到D的區段內列車上都有N個或N個以上的空座位時該售票申請才被受理。請你寫一個程序，實現這個自動 售票系統。
<p align="left">【輸入格式】
第一行包含三個用空格隔開的整數C、S和R，其中1≤C≤60000， l≤S≤60000，1≤R≤60000。C爲城市個數，S爲列車上的座位數，R爲所有售票申請總數。接下來的R行每行爲一個售票申請，用三個由空格隔開 的整數O，D和N表示，O爲起始站，D 爲目的地站，N爲車票站數，其中1≤D≤C，1≤O≤C，所有的售票申請按申請的時間從早到晚給出。

【輸出格式】
輸出共有R行，每行輸出一個“YES”或“NO”，表示當前的售票申請被受理或不被受理。

【輸入輸出樣例】
<strong>
</strong>輸入:
4 6 4
1 4 2
1 3        2
2 4 3
1 2  3

輸出:
YES
YES
NO
NO</div>