<p><img alt="" src="https://assets.leetcode.com/uploads/2020/07/09/change.png" style="width: 635px; height: 312px;" /></p>

<p>Winston was given the above mysterious function <code>func</code>. He has an integer array <code>arr</code> and an integer <code>target</code> and he wants to find the values <code>l</code> and <code>r</code> that make the value <code>|func(arr, l, r) - target|</code> minimum possible.</p>

<p>Return <em>the minimum possible value</em> of <code>|func(arr, l, r) - target|</code>.</p>

<p>Notice that <code>func</code> should be called with the values <code>l</code> and <code>r</code> where <code>0 &lt;= l, r &lt; arr.length</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> arr = [9,12,3,7,15], target = 5
<strong>Output:</strong> 2
<strong>Explanation:</strong> Calling func with all the pairs of [l,r] = [[0,0],[1,1],[2,2],[3,3],[4,4],[0,1],[1,2],[2,3],[3,4],[0,2],[1,3],[2,4],[0,3],[1,4],[0,4]], Winston got the following results [9,12,3,7,15,8,0,3,7,0,0,3,0,0,0]. The value closest to 5 is 7 and 3, thus the minimum difference is 2.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> arr = [1000000,1000000,1000000], target = 1
<strong>Output:</strong> 999999
<strong>Explanation:</strong> Winston called the func with all possible values of [l,r] and he always got 1000000, thus the min difference is 999999.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> arr = [1,2,4,8,16], target = 0
<strong>Output:</strong> 0
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= arr.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= arr[i] &lt;= 10<sup>6</sup></code></li>
	<li><code>0 &lt;= target &lt;= 10<sup>7</sup></code></li>
</ul>

typedef long long ll;

class SegTree {
public:
  int left_most, right_most;
  SegTree *left_child, *right_child;
  ll res;

  SegTree(int left, int right, vector<int> &v) {
    left_most = left;
    right_most = right;
    if (left_most == right_most) {
      res = v[left];
      left_child = nullptr;
      right_child = nullptr;
    } else {
      int mid = (left + right) / 2;
      left_child = new SegTree(left_most, mid, v);
      right_child = new SegTree(mid + 1, right_most, v);
      recalc();
    }
  }

  void recalc() {
    if (left_most == right_most)
      return;
    // TODO
    res = left_child->res & right_child->res;
  }

  void update(int index, int new_val) {
    if (left_most == right_most) {
      res = new_val;
      return;
    }

    if (index <= left_child->right_most)
      left_child->update(index, new_val);
    else
      right_child->update(index, new_val);
    recalc();
  }

  ll query(int l, int r) {
    if (l > right_most || r < left_most)
        return INT_MAX;
    if (l <= left_most && r >= right_most)
      return res;
    // TODO
    return left_child->query(l, r) & right_child->query(l, r);
  }

  ~SegTree() {
    if (left_child != nullptr)
      delete left_child;
    if (right_child != nullptr)
      delete right_child;
  }
};

class Solution {
public:
    int closestToTarget(vector<int>& arr, int target) {
        SegTree st(0, arr.size() - 1, arr);
        auto bin_search = [&](int i) {
            int l = 0, r = arr.size() - 1;
            int ans = INT_MAX;
            while (l <= r) {
                int m = (l + r) / 2;
                int res = st.query(i, m);
                ans = min(ans, abs(res - target));
                if (res > target) {
                    l = m + 1;
                } else {
                    r = m - 1;
                }
            }
            return ans;
        };
        int ans = INT_MAX;
        for (int i = 0; i < arr.size(); i++) {
            ans = min(ans, bin_search(i));
        }
        return ans;
    }
};
207000