Throughout the last several weeks I have tried to invent, and tackle, a generalization of segment trees (although now it doesn't fit to name it "segment trees"... see for yourself). The results are very few and special-purposed (and not so good, if you ask me), but the problem was very appealing and fun to think about.
The purpose of this blogpost is to share my experience with this problem, in order to strike curiousity in at least a few people, and also to let bright-minded users tackle this problem together, and possibly achieve better results.
So, there is no tl;dr. Sorry :)