火车售票问题

某次列车途经C个城市，城市编号依次为1到C，列车上共有S个座位，铁路局规定售出的车票只能是坐票，即车上所有的旅客都有座，售票系统是由计算机执行的，每一个售票申请包含三个参数，分别用O、D、N表示，O为起始站，D为目的地站，N为车票张数，售票系统对该售票申请作出受理或不受理的决定，只有在从O到D的区段内列车上都有N个或N个以上的空座位时该售票申请才被受理，请你写一个程序，实现这个自动售票系统。

提示：售票查询时间复杂度log(n) n为城市数目

线段树求解，建立线段树，线段树父节点记录所有孩子的最大值，需要一些技巧实现最大值的更新。
代码：
struct SEGMENT
{
        int nFrom;
        int nTo;
        int nMaxTickets;
        int nPassDown;

        SEGMENT(int nf = 0, int nt = 0) : nFrom(nf), nTo(nt)
        { nMaxTickets = 0; nPassDown = 0; }
};

class CTicketSystem
{
public:
        CTicketSystem(int nCities, int nSits);
        ~CTicketSystem() { delete []m_pTree; }

public:
        bool BuyTicket(int nBeg, int nEnd, int n);

private:
        void _inner_build(int nIndex, int nBeg, int nEnd);
        bool _inner_judge(int nIndex, int nBeg, int nEnd, int n, int nPassDownSum);
        void _inner_add(int nIndex, int nBeg, int nEnd, int n);

private:
        SEGMENT* m_pTree;
        int m_nCities;
        const int m_nSits;
};

inline CTicketSystem::CTicketSystem(int nCities, int nSits) : m_nCities(nCities), m_nSits(nSits)
{
        assert(nCities>0);
        assert(nSits>0);

        m_pTree = new SEGMENT[3*nCities];
        _inner_build(0, 0, m_nCities-1);
}

inline void CTicketSystem::_inner_build(int nIndex, int nBeg, int nEnd)
{
        m_pTree[nIndex].nFrom = nBeg;
        m_pTree[nIndex].nTo = nEnd;

        if (nBeg == nEnd) return;

        _inner_build(2*nIndex+1, nBeg, (nBeg+nEnd)/2);
        _inner_build(2*nIndex+2, (nBeg+nEnd)/2+1, nEnd);
}

inline bool CTicketSystem::BuyTicket(int nBeg, int nEnd, int n)
{
        assert(nBeg>=0 && nEnd>=0 && nEnd>=nBeg && n>0);

        if (_inner_judge(0, nBeg, nEnd, n, 0))
        {
                _inner_add(0, nBeg, nEnd, n);
                return true;
        }

        return false;
}

bool CTicketSystem::_inner_judge(int nIndex, int nBeg, int nEnd, int n, int nPassDownSum)
{
        nPassDownSum += m_pTree[nIndex].nPassDown;
        if (m_pTree[nIndex].nFrom == nBeg && m_pTree[nIndex].nTo == nEnd)
                return nPassDownSum + n <= m_nSits;

        int nMid = (m_pTree[nIndex].nFrom + m_pTree[nIndex].nTo)/2;
        if (nMid >= nEnd)
                return _inner_judge(2*nIndex+1, nBeg, nEnd, n, nPassDownSum);
       
        if (nMid < nBeg)
                return _inner_judge(2*nIndex+2, nBeg, nEnd, n, nPassDownSum);

        return _inner_judge(2*nIndex+1, nBeg, nMid, n, nPassDownSum) && _inner_judge(2*nIndex+2, nMid+1, nEnd, n, nPassDownSum);
}

void CTicketSystem::_inner_add(int nIndex, int nBeg, int nEnd, int n)
{
        if (m_pTree[nIndex].nFrom == nBeg && m_pTree[nIndex].nTo == nEnd)
        {
                m_pTree[nIndex].nMaxTickets += n;
                m_pTree[nIndex].nPassDown += n;
                return;
        }

        int nMid = (m_pTree[nIndex].nFrom + m_pTree[nIndex].nTo)/2;
        if (nMid >= nEnd)
        {
                _inner_add(2*nIndex+1, nBeg, nEnd, n);
                m_pTree[nIndex].nMaxTickets =
                        m_pTree[nIndex].nMaxTickets > m_pTree[2*nIndex+1].nMaxTickets ? m_pTree[nIndex].nMaxTickets : m_pTree[2*nIndex+1].nMaxTickets;
                return;
        }

        if (nMid < nBeg)
        {
                _inner_add(2*nIndex+2, nBeg, nEnd, n);
                m_pTree[nIndex].nMaxTickets =
                        m_pTree[nIndex].nMaxTickets > m_pTree[2*nIndex+2].nMaxTickets ? m_pTree[nIndex].nMaxTickets : m_pTree[2*nIndex+2].nMaxTickets;
                return;
        }

        _inner_add(2*nIndex+1, nBeg, nMid, n);
        _inner_add(2*nIndex+2, nMid+1, nEnd, n);

        m_pTree[nIndex].nMaxTickets =
                m_pTree[nIndex].nMaxTickets > m_pTree[2*nIndex+1].nMaxTickets ? m_pTree[nIndex].nMaxTickets : m_pTree[2*nIndex+1].nMaxTickets;
        m_pTree[nIndex].nMaxTickets =
                m_pTree[nIndex].nMaxTickets > m_pTree[2*nIndex+2].nMaxTickets ? m_pTree[nIndex].nMaxTickets : m_pTree[2*nIndex+2].nMaxTickets;
}

膜拜线段树……这玩意总是学不会啊