Changed permalink structure of CPT – should I redirect?

I concur that you need to add a redirect. You can do this easily with the following function. I’m sure you will have to tweak it, but it’s a good proof-of-concept.

add_action('parse_request', 'redirect_books_to_fiction', 0);
function  redirect_books_to_fiction(){
    global $wp;
    if(preg_match_all('~literature\/(.+)/(.+)?~', $wp->request, $matches)){
        $redirect = get_bloginfo('siteurl')."https://wordpress.stackexchange.com/".str_replace('books', 'fiction', $wp->request);
        wp_redirect($redirect, 301);
        exit;
    }
}

To further answer you question regarding matching segments:

add_action('parse_request', 'redirect_cpts', 0);
function  redirect_cpts(){
    $one_to_one = array(
        'literature' => 'books',
        'food' => 'foo',
        'bar' => 'food'
    );
    $request = $_SERVER['REQUEST_URI'];

    //We limit the scope of the regex to our specified CPTs so we don't hammer every request
    if(preg_match_all('~(literature|food|bar)/(.+)/(.+)?~', $request, $matches)){
        if(!$one_to_one[$matches[1][0]])
            return;

        $post_type = $one_to_one[$matches[1][0]]; //Do proper escaping
        $post_name = $matches[3][0]; //Do proper escaping

        if($post_name && $post_type){
            global $wpdb;
            $post = $wpdb->get_row("SELECT * ID FROM $wpdb->posts WHERE post_type="$post_type" AND post_name="$post_name"");
            $redirect = get_permalink($post);
            if($redirect){
                wp_redirect($redirect, 301);
                exit;
            }
        }
    }
}