utkarshl

#include"cassert"
#include"vector"
typedef unsigned int I32;
typedef I32* P32;
template <typename T, int beginidx=0> // in case vertices of graph are like 1, 2, 3 ..., beginidx becomes 1
class LCA {
    P32 height, pathno, head, ancestor, log;
    std::vector<I32>* paths;
    const I32 ulim, root;
    const T* const G;

utkarshl

#include"segment_tree.cpp"
#include"map"
#include"algorithm"
#include"stdio.h"
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
struct query{char op[2]; int x;};
struct node{
  int num_active_leaves;
	void merge(node& a, node& b){

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;

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"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

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

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

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

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 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)