kien_coi_1997's blog

Segment tree with insertion and deletion operators.
By kien_coi_1997, 10 years ago, In English

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.

  • Vote: I like it
  • +22
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

In fact it is implicit binary balanced tree like implicit cartesian tree where key=amount of elements, that less than value, isn't it?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, it is called indexable AVL tree. With other structures, we have: indexable splay tree, indexable skip list, ...

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please elaborate how do we go about adding the remove method here? I understand that remove should take an index and remove element at that index from tree.

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        I haven't use this structure for a long time. Therefore, it can have some mistakes. But the idea is correct.


        int remove(int u) { // return proper id
  if (ll>u || u>rr) return id; // nothing changed
  if (ll==rr) return 0; // delete id
  Right[id] = right().remove(u);
  Left[id] = left().remove(u);
  if (!Left[u] || !Right[u]) // when one child is NULL (deleted),
    return Left[u] | Right[u]; // return the remaining
  update(id); return id; // don't forget to return
}

        Some important notes:

        • Function remove should return id of node.
        • Call right().remove(u) first, left().remove(u) after.
        • Pay attention when a child of a node is deleted.
        • DO NOT leave a node having only a child.
        • Don't need to re-balance, it is not essential in operator remove, unless you understand this structure well.
        → Reply