I have created this structure successfully some weeks ago, and I want to share it with you. This structure is fast, efficient, and it is only the improvement from segment tree. I have used this code to submit to two problems, one is in SPOJ, one is in CF. For simpliest example, consider the problem QMAX3VN on SPOJ. (http://www.spoj.com/problems/QMAX3VN/)

There are two operators: Insert X before Y-th element, and find Max between X-th element and Y-th element (inclusively).

Firstly, I use a variant of segment tree, allow us to insert element and access elements by indexes. Each node will have two childs: Left[Node] and Right[Node], by default, they are 0 (NULL). To be indexable, we must maintain array Size[].

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;

#define long long long
#define f1(i,n) for (int i=1; i<=n; i++)
#define f0(i,n) for (int i=0; i<n; i++)

#define N 400005
#define oo 0x3c3c3c3c
int Max[N], Size[N], Height[N], Left[N], Right[N], Peak;

void update(int id){
   int ll=Left[id], rr=Right[id];
   Max[id]=max(Max[ll], Max[rr]);
   Size[id]=Size[ll]+Size[rr];
   Height[id]=max(Height[ll], Height[rr])+1;
}

int create(int Value){
   int id = ++Peak;
   Max[id]=Value;
   Size[id]=1;
   return id;
}

struct node {
   int ll, rr, id;
   node (int L, int X) { ll=L, id=X; rr=ll+Size[id]-1; }
   node left(){ return node(ll, Left[id]); }
   node right(){ return node(ll+Size[Left[id]], Right[id]); }

   void insert(int u, int Value) {
      if (ll>u || u>rr) return ;
      if (ll==rr) {
         Left[id]=create(Value);
         Right[id]=create(Max[id]);
         update(id); return ;
      }
      left().insert(u, Value);
      right().insert(u, Value);
      update(id);
   }

   int max_range(int L, int R) {
      if (L>rr || ll>R || L>R) return -oo;
      if (L<=ll && rr<=R) return Max[id];
      int Max1 = left().max_range(L, R);
      int Max2 = right().max_range(L, R);
      return max(Max1, Max2);
   }
};

ostream& operator << (ostream& cout, node a){
   if (a.ll==a.rr) return cout << Max[a.id];
   return cout << "(" << a.left() << " " << a.right() << ")";
   //return cout << a.left() << " " << a.right();
}

main(){
   create(-oo);
   int m; scanf("%d", &m);
   while (m--){
      char c; int x, y;
      scanf(" %c%d%d", &c, &x, &y);

      if (c=='A') node(1, 1).insert(y, x);
      else printf("%d\n", node(1, 1).max_range(x, y));
//    cout << node(1,1) << endl;
   }
}

In average case, each operators will be O(logn), but in worst case, complexity is O(n), then we will get TLE on problem QMAX3VN. I will use tree rotations in AVL tree to balance tree. Magiccally, the addtional functions are very independent with our old code. Here is some functions we need to add, it is not different from AVL tree:

int link(int ll, int u, int rr){
   Left[u]=ll, Right[u]=rr;
   return update(u), u;
}

int right_rotate(int u){ 
   int ll = Left[u]; 
   return link(Left[ll], ll, link(Right[ll], u, Right[u]));
}

int left_rotate(int u){
   int rr = Right[u];
   return link(link(Left[u], u, Left[rr]), rr, Right[rr]);
}

int balance(int u){
   if (abs(Height[Left[u]]-Height[Right[u]])<=1) return u;
   bool x=Height[Left[u]]>Height[Right[u]];
   int v=(x?Left[u]:Right[u]);
   bool y=Height[Left[v]]>Height[Right[v]];
   if (x && y) u=right_rotate(u);
   if (!x && !y) u=left_rotate(u);
   if (x && !y) { Left[u]=v=left_rotate(v); u=right_rotate(u); }
   if (!x && y) { Right[u]=v=right_rotate(v); u=left_rotate(u); }
   return u;
}

And add only two statement into Insert operator:

   void insert(int u, int Value) {
      if (ll>u || u>rr) return ;
      if (ll==rr) {
         Left[id]=create(Value);
         Right[id]=create(Max[id]);
         update(id); return ;
      }
      left().insert(u, Value);
      right().insert(u, Value);
      Left[id]=balance(Left[id]); // this one
      Right[id]=balance(Right[id]); // and this
      update(id);
   }

This is my accepted solution in problem QMAX3VN: https://sites.google.com/site/kc97ble/container/segmenttree-cpp/segmenttree-cpp-7-avl

I have used this structure to submit successully to a problem in CF. It is problem L in http://codeforces.net/gym/100125. I implemented three operator: Insert, Remove, get OR-Sum. This is my solution http://codeforces.net/gym/100125/submission/6520803.

Hope that it would be useful.