Index: lib/dataStructure/segmentTree.cpp
==================================================================
--- lib/dataStructure/segmentTree.cpp
+++ lib/dataStructure/segmentTree.cpp
@@ -1,13 +1,109 @@
 //-------------------------------------------------------------
 // Segment tree
 //   in some general form
 //
 // Verified by
+//   - Codeforces 107 C
 //   - Codeforces 104 E
 //-------------------------------------------------------------
 
+template<typename Node>
+class SegmentTree
+{
+public:
+	template<typename Seq>
+	SegmentTree(const Seq& s) {
+		int N = 1;
+		while( N < s.size() )
+			N <<= 1;
+
+		tree.resize(tree.size()+1); tree.back().resize(N);
+		for(int i=0; i<N; ++i)
+			tree.back()[i] = i<s.size() ? Node::One(s[i]) : Node::Zero();
+
+		while(N>>=1) {
+			tree.resize(tree.size()+1); tree.back().resize(N);
+			for(int i=0; i<N; ++i)
+				CalcMidNode(tree.size()-1, i);
+		}
+	}
+
+	Node Query(int s, int e) { // compute h( seq[s,e) ) : O(log n)
+		return QueryRec(s, e, tree.size()-1, 0, tree[0].size());
+	}
+
+	template<typename Value>
+	void Set(int s, int e, Value v) { // seq[s,e):=v : O(log n�E|e-s|)
+		SetRec(s, e, Node::One(v), tree.size()-1, 0, tree[0].size());
+	}
+
+private:
+	void CalcMidNode(int lv, int idx)
+	{
+		tree[lv][idx] = Node::Concat(tree[lv-1][idx*2], tree[lv-1][idx*2+1]);
+	}
+
+	Node QueryRec(int s, int e, int lv, int idx, int stride)
+	{
+		const int myL = stride*idx;
+		const int myR = stride*(idx+1);
+		if( e<=myL || myR<=s )
+			return Node::Zero();
+		if( s<=myL && myR<=e )
+			return tree[lv][idx];
+		return Node::Concat(QueryRec(s,e,lv-1,idx*2,stride/2),
+		                    QueryRec(s,e,lv-1,idx*2+1,stride/2));
+	}
+
+	void SetRec(int s, int e, const Node& n, int lv, int idx, int stride)
+	{
+		const int myL = stride*idx;
+		const int myR = stride*(idx+1);
+		if( e<=myL || myR<=s )
+			return;
+		if( stride == 1 ) {
+			tree[lv][idx] = n;
+		} else {
+			SetRec(s,e,n,lv-1,idx*2,stride/2);
+			SetRec(s,e,n,lv-1,idx*2+1,stride/2);
+			CalcMidNode(lv, idx);
+		}
+	}
+
+	vector< vector<Node> > tree;
+};
+
+struct Node
+{
+	double sum;
+	double maxLeft;
+	double maxRight;
+	double maxSum;
+	static Node Zero()
+	{
+		Node c = {0, 0, 0, 0};
+		return c;
+	}
+	static Node One(double v)
+	{
+		Node c = {v, max(0.0,v), max(0.0,v), max(0.0,v)};
+		return c;
+	}
+	static Node Concat(const Node& l, const Node& r)
+	{
+		Node c = {
+			l.sum + r.sum,
+			max(l.maxLeft, l.sum+r.maxLeft),
+			max(l.maxRight+r.sum, r.maxRight),
+			max(max(l.maxSum, r.maxSum), l.maxRight+r.maxLeft),
+		};
+		return c;
+	}
+};
+
+/*
 class SegmentTree
 {
 	// --- DATA FOR EACH NODE ---
 	struct Node
 	{
@@ -106,5 +202,6 @@
 		SwitchRec(Stride/2, lv-1, idx*2,   Raw_L, Raw_R);
 		SwitchRec(Stride/2, lv-1, idx*2+1, Raw_L, Raw_R);
 		UpdateMidNode(lv, idx);
 	}
 };
+*/