/**
* Definition of SegmentTreeNode:
* class SegmentTreeNode {
* public:
* int start, end, count;
* SegmentTreeNode *left, *right;
* SegmentTreeNode(int start, int end, int count) {
* this->start = start;
* this->end = end;
* this->count = count;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
/**
*@param root, start, end: The root of segment tree and
* an segment / interval
*@return: The count number in the interval [start, end]
*/
int query(SegmentTreeNode *root, int start, int end) {
// write your code here
if(root == NULL) { return 0; }
if(start > end || start > root->end || end < root->start) { return 0; }
if(start <= root->start && end >= root->end) { return root->count; }
int mid = (root->start + root->end) / 2;
int left = query(root->left, start, min(mid, end));
int right = query(root->right, max(mid, start), end);
return left+right;
}
};
lintcode-Segment Tree Query II
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
- 文/潘曉璐 我一進(jìn)店門婆排，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人笔链，你說我怎么就攤上這事段只。” “怎么了鉴扫？”我有些...
- 文/不壞的土叔 我叫張陵赞枕，是天一觀的道長。 經(jīng)常有香客問我坪创，道長炕婶，這世上最難降的妖魔是什么？ 我笑而不...
- 正文 為了忘掉前任莱预，我火速辦了婚禮柠掂，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘依沮。我一直安慰自己涯贞，他們只是感情好枪狂，可當(dāng)我...
- 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著宋渔，像睡著了一般州疾。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上皇拣，一...
- 文/蒼蘭香墨 我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼钾恢！你這毒婦竟也來了手素？” 一聲冷哼從身側(cè)響起，我...
- 正文 年R本政府宣布棚贾，位于F島的核電站，受9級特大地震影響榆综，放射性物質(zhì)發(fā)生泄漏妙痹。R本人自食惡果不足惜，卻給世界環(huán)境...
- 文/蒙蒙 一鼻疮、第九天 我趴在偏房一處隱蔽的房頂上張望细诸。 院中可真熱鬧，春花似錦陋守、人聲如沸震贵。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽猩系。三九已至，卻和暖如春中燥，著一層夾襖步出監(jiān)牢的瞬間寇甸，已是汗流浹背。 一陣腳步聲響...
推薦閱讀更多精彩內(nèi)容
- 原題 對于一個數(shù)組沪铭，我們可以對其建立一棵線段樹, 每個結(jié)點存儲一個額外的值count來代表這個結(jié)點所指代的數(shù)組區(qū)間...
- 原題 LintCode 70. Binary Tree Level Order Traversal II Desc...
- 原題 對于一個有n個數(shù)的整數(shù)數(shù)組，在對應(yīng)的線段樹中, 根節(jié)點所代表的區(qū)間為0-n-1, 每個節(jié)點有一個額外的屬性m...
- 【題目描述】 For an array, we can build a Segment Tree for it, ...
- 綿綿翩翩 飄飛的絲雨 織成一張無盡透明的網(wǎng) 網(wǎng)住漂泊不定的念 網(wǎng)住慌亂無措的淚 網(wǎng)住故作鎮(zhèn)定的情
