utkarshl

void update_single_node(node& n, int new_val){
	n.val = new_val;
}
void range_update(int root, int left_most_leaf, int right_most_leaf, int u, int v, int new_val)
{
	if(u<=left_most_leaf && right_most_leaf<=v)
		return update_single_node(tree[root], new_val);
	int mid = (left_most_leaf+right_most_leaf)/2,
		left_child = root*2,
		right_child = left_child+1;

utkarshl

struct node
{
	int segmentSum,bestPrefix,bestSuffix,bestSum;
	node split(node& l, node& r){}
	node merge(node& l, node& r)
	{
		segmentSum = l.segmentSum + r.segmentSum;
		bestPrefix = max( l.segmentSum + r.bestPrefix , l.bestPrefix );
		bestSuffix = max( r.segmentSum + l.bestSuffix , r.bestSuffix );
		bestSum    = max( max( l.bestSum , r.bestSum) , l.bestSuffix + r.bestPrefix );

utkarshl

struct node
{
        int min, add;
        split(const node& a, const node& b)
        {
                a.add+=add,  a.min+=add,
                b.add+=add,  b.min+=add;
                add=0;
        }
        void merge(node a, node b)

utkarshl

void splitdown(int postn)
{
        if(postn>1) splitdown(postn>>1);
        tree[postn].split(tree[2*postn],tree[2*postn+1]);
}
void update(int postn, node nd)
{
        postn += 1<<n;
        splitdown(postn>>1);
        tree[postn] = nd;

utkarshl

struct node
{
        int numleaves, add, sum;
        void split(node& l, node& r)
        {
                l.add += add;
                l.sum += add * l.numleaves;
                r.add += add;
                r.sum += add * r.numleaves;
                add=0;

utkarshl

struct node{
        int num_active_leaves;
        void split(node& l, node& r){}
        void merge(node& l, node& r){
                num_active_leaves = l.num_active_leaves + r.num_active_leaves;
        }
        bool operator<(const node& n)const{
                return num_active_leaves < n.num_active_leaves;
        }
};

utkarshl

In order to use segtree class defined above, you will need to create a datatype(a struct most likely), which will implement the function merge(). It can also additionally implement split, if you need to define the split operation.
A sample is shown as "struct segtree_node" in the code above.

The segtree has to be instantiated with this defined data type. For example,as 
segtree<segtree_node> s;

You have to first call the init function of the class, which will take 
  int n=number of elements in your array,
  node[] = your inital array,
  identity = an element such that merge(y,identity) = merge(identity,y) = y for all y's.

utkarshl

#include"segment_tree.cpp"
#include"algorithm"
#include"stdio.h"
struct node{
  int min,sum;
	void merge(node& l,node& r){
		sum = l.sum+r.sum;
		min = std::min(l.min,l.sum+r.min);
	}
};

utkarshl

struct node{
	int val;
	void split(node& l, node& r){}
	void merge(node& a, node& b)
	{
		val = min( a.val, b.val );
	}
}tree[1<<(n+1)];
node range_query(int root, int left_most_leaf, int right_most_leaf, int u, int v)
{

utkarshl

#include"segment_tree.cpp"
#include"stdio.h"
#include"algorithm"
struct node{
  long long add,sum;
	int numleaves;
	void merge(node& l, node& r){
		add=0;
		sum = l.sum + r.sum;
		numleaves = l.numleaves + r.numleaves;