Proof of concept on using skip lists as segment trees. (RMQ is given as an example)

skiplist_segtree.cpp

#include<random>
#include<vector>
using namespace std;
using ll=long long;

struct FakeSkipList
{
	struct NodePack
	{
		int H=1;
		vector<int>prev,range;
		vector<ll>node;
	};
	vector<NodePack>data;
	mt19937 gen;
	bernoulli_distribution bin;
	vector<int>h_last;
	const ll identity=2000000000ll;
	void push_back(ll v)
	{
		data.emplace_back();
		int cur=data.size()-1;
		NodePack&B=data.back();
		
		while(bin(gen))B.H++;
		B.prev.resize(B.H,-1);
		B.node.resize(B.H,identity);
		B.range.resize(B.H,1);
		for(int i=0;i<B.H;i++)
		{
			B.prev[i]=h_last[i];
			if(h_last[i]>=0)
			data[h_last[i]].range[i]=cur-h_last[i];
			h_last[i]=cur;
		}
		int h=0,i=cur;
		while(i>=0)
		{
			if(data[i].H<h+1)break;
			data[i].node[h]=min(data[i].node[h],v);
			if(data[i].H>h+1)h++;
			else
			{
				while(data[i].H==h+1&&data[i].prev[h]>=0)
				i=data[i].prev[h];
				h++;
			}
		}
	}
	FakeSkipList(vector<ll>&vec)
	{
		gen.seed(150);
		for(int i=0;i<64;i++)h_last.push_back(-1);
		for(ll a:vec)push_back(a);
		for(int i=0;i<64&&h_last[i]>=0;i++)
		data[h_last[i]].range[i]=vec.size()-h_last[i];
	}
	ll query(int l,int r)
	{
		int idx=l;ll ans=identity;
		while(idx<=r)
		{
			int h=data[idx].H-1;
			while(h>=0&&idx+data[idx].range[h]>r)h--;
			if(h<0)return ans;
			ans=min(ans,data[idx].node[h]);
			idx+=data[idx].range[h];
		}
		return ans;
	}
	void update(int i,ll k)
	{
		int h=0;
		while(i>=0)
		{
			if(data[i].H<h+1)break;
			data[i].node[h]=k;
			k=identity;
			while(i+data[i].range[h]<data.size()
			&&data[i+data[i].range[h]].H==h+1)
			i+=data[i].range[h];
			
			while(i>=0&&data[i].H==h+1)
			{
				k=min(k,data[i].node[h]);
				if(data[i].prev[h]<0)break;
				i=data[i].prev[h];
				if(data[i].H>h+1)break;
			}
			k=min(k,data[i].node[h]);
			h++;
		}
	}
};