I have an idea how to implement sub array reverse with O(1), not including precalculation such as reading the input. I will have many reverse operations, and I can't use the trivial solution of O(N).Edit: To be more clear I want to build data structure behind the array with access layer that knows about reversing requests and inverts the indexing logic as necessary when someone wants to iterate over the array.Edit 2: The data structure will only be used for iterationsI been reading this and this and even this questions but they aren't helping.There are 3 cases that need to be taking care of:Regular reverse operationReverse that including reversed areaIntersection between reverse and part of other reversed area in the arrayHere is my implementation for the first two parts, I will need your help with the last one.This is the rule class:class Rule {    public int startingIndex;    public int weight;}It is used in my basic data structure City:public class City {    Rule rule;    private static AtomicInteger _counter = new AtomicInteger(-1);    public final int id = _counter.incrementAndGet();    @Override    public String toString() {        return  + id;    }}This is the main class:public class CitiesList implements Iterable<City>, Iterator<City> {    private int position;    private int direction = 1;    private ArrayList<City> cities;    private ArrayDeque<City> citiesQeque = new ArrayDeque<>();    private LinkedList<Rule> rulesQeque = new LinkedList<>();    public void init(ArrayList<City> cities) {        this.cities = cities;    }    public void swap(int index1, int index2){        Rule rule = new Rule();        rule.weight = Math.abs(index2 - index1);        cities.get(index1).rule = rule;        cities.get(index2 + 1).rule = rule;    }    @Override    public void remove() {        throw new IllegalStateException(Not implemented);    }    @Override    public City next() {        City city = cities.get(position);        if (citiesQeque.peek() == city){            citiesQeque.pop();            changeDirection();            position += (city.rule.weight + 1) * direction;            city = cities.get(position);        }        if(city.rule != null){            if(city.rule != rulesQeque.peekLast()){                rulesQeque.add(city.rule);                position += city.rule.weight * direction;                changeDirection();                citiesQeque.push(city);            }            else{                rulesQeque.removeLast();                position += direction;            }        }        else{            position += direction;        }        return city;    }    private void changeDirection() {        direction *= -1;    }    @Override    public boolean hasNext() {        return position < cities.size();    }    @Override    public Iterator<City> iterator() {        position = 0;        return this;    }}And here is a sample program:public static void main(String[] args) {        ArrayList<City> list = new ArrayList<>();        for(int i = 0 ; i < 20; i++){            list.add(new City());        }        CitiesList citiesList = new CitiesList();        citiesList.init(list);        for (City city : citiesList) {            System.out.print(city +  );        }        System.out.println(\n******************);        citiesList.swap(4, 8);        for (City city : citiesList) {            System.out.print(city +  );        }        System.out.println(\n******************);        citiesList.swap(2, 15);        for (City city : citiesList) {            System.out.print(city +  );        }    }How do I handle reverse intersections?
Reverse subarray of an array with O(1)
java;algorithms;sorting;array
You could use a xor linked list variant (using indexes into an array for the pointer).Then reversing is easy:reverse(int city1prev, int city1index, int city2prev, int city2index){    int city1next = array[city1index].ptr^city1prev;    int city2next = array[city2index].ptr^city2prev;    city1.ptr = city2next^city1next;    city2.ptr = city2prev^city1prev;    array[city1prev].ptr^= city1index^city2index;    array[city2next].ptr^= city1index^city2index;}The downside is (as with all linked list implementations) that indexing into it is O(n).This will reverse the sub array due to how the xor link works: city2 will be where city1 used to be and city2prev will be after it and so on. So the new sequence becomes: city1prev, city2, city2prev,..., city1next, city1, city2next.      Key point is that there is no difference between traversing a xor linked list forward or backward (you keep a index to the current and the previous items and you get the next by doing array[current].ptr^previous).