✅ Easy Segment Tree Approach| Intuitive Solution| C++ code
Intuition\nSince its a range query and update so we should think of Segment tree approach\n# Approach\nSince its given that we can multiply the array elements b
# Intuition\nSince its a range query and update so we should think of Segment tree approach\n# Approach\nSince its given that we can multiply the array elements by 2, it indirectly means that we can right shift the array elements k times.\nNow,\nFirstly we should think how many values should be affected by the operation?\nSo the answer to this is it is always optimal to right shift that value which has the most significant bit as leftmost as possible then the other elements\n\nSo to do so,\nWe build the segment tree for Bitwise OR operation and for each value we right shift that particular element k times and check for the maximum value\n\n# Complexity\n- Time complexity:\nO(n*logn)\n\n- Space complexity:\nO(n)\n\n# Code\n```\n#define ll long long\n#include <vector>\nusing namespace std;\n\nclass SegmentTree {\nprivate:\n    vector<ll> tree;\n    ll n;\n    \npublic:\n    SegmentTree(ll sz) {\n        n = sz;\n        tree.resize(4*n);\n    }\n    \n    void update(ll idx, ll val) {\n        updateUtil(1, 0, n-1, idx, val);\n    }\n    \n    ll query(int l, int r) {\n        return queryUtil(1, 0, n-1, l, r);\n    }\n    \nprivate:\n    void updateUtil(ll node, ll start, ll end, ll idx, ll val) {\n        if (start == end) {\n            tree[node] = val;\n        } else {\n            ll mid = (start + end) / 2;\n            if (idx <= mid) {\n                updateUtil(2*node, start, mid, idx, val);\n            } else {\n                updateUtil(2*node+1, mid+1, end, idx, val);\n            }\n            tree[node] = tree[2*node] | tree[2*node+1];\n        }\n    }\n    \n    ll queryUtil(ll node, ll start, ll end, ll l, ll r) {\n        if (r < start || end < l) {\n            return 0;\n        }\n        if (l <= start && end <= r) {\n            return tree[node];\n        }\n        ll mid = (start + end) / 2;\n        ll orLeft = queryUtil(2*node, start, mid, l, r);\n        ll orRight = queryUtil(2*node+1, mid+1, end, l, r);\n        return orLeft | orRight;\n    }\n};\n\n\nclass Solution {\npublic:\n    long long maximumOr(vector<int>& nums, int k) {\n        ll n=nums.size();\n            SegmentTree st(n);\n         for (int i = 0; i < n; i++) {\n        st.update(i, nums[i]);\n        }\n        \n        ll ans=0;\n        for(int i=0;i<n;i++){\n            int val=nums[i];\n            st.update(i,((1ll * val) << k));\n            ll anss=st.query(0,n-1);\n            ans=max(ans,anss);\n            st.update(i,val);\n        }\n        \n        \n        return ans;\n        \n\n    }\n};\n```\n\nPlease UPVOTE it you liked my solution :)
['C++']