29d4d2b5.7ce2da02.js

(window.webpackJsonp=window.webpackJsonp||[]).push([[13],{147:function(e,n,t){"use strict";function r(){return(r=Object.assign||function(e){for(var n=1;n<arguments.length;n++){var t=arguments[n];for(var r in t)Object.prototype.hasOwnProperty.call(t,r)&&(e[r]=t[r])}return e}).apply(this,arguments)}t.d(n,"a",(function(){return r}))},148:function(e,n,t){"use strict";t.d(n,"a",(function(){return f})),t.d(n,"b",(function(){return p}));var r=t(0),i=t.n(r);function a(e,n,t){return n in e?Object.defineProperty(e,n,{value:t,enumerable:!0,configurable:!0,writable:!0}):e[n]=t,e}function s(e,n){var t=Object.keys(e);if(Object.getOwnPropertySymbols){var r=Object.getOwnPropertySymbols(e);n&&(r=r.filter((function(n){return Object.getOwnPropertyDescriptor(e,n).enumerable}))),t.push.apply(t,r)}return t}function o(e){for(var n=1;n<arguments.length;n++){var t=null!=arguments[n]?arguments[n]:{};n%2?s(Object(t),!0).forEach((function(n){a(e,n,t[n])})):Object.getOwnPropertyDescriptors?Object.defineProperties(e,Object.getOwnPropertyDescriptors(t)):s(Object(t)).forEach((function(n){Object.defineProperty(e,n,Object.getOwnPropertyDescriptor(t,n))}))}return e}function u(e,n){if(null==e)return{};var t,r,i=function(e,n){if(null==e)return{};var t,r,i={},a=Object.keys(e);for(r=0;r<a.length;r++)t=a[r],n.indexOf(t)>=0||(i[t]=e[t]);return i}(e,n);if(Object.getOwnPropertySymbols){var a=Object.getOwnPropertySymbols(e);for(r=0;r<a.length;r++)t=a[r],n.indexOf(t)>=0||Object.prototype.propertyIsEnumerable.call(e,t)&&(i[t]=e[t])}return i}var l=i.a.createContext({}),c=function(e){var n=i.a.useContext(l),t=n;return e&&(t="function"==typeof e?e(n):o(o({},n),e)),t},f=function(e){var n=c(e.components);return i.a.createElement(l.Provider,{value:n},e.children)},m={inlineCode:"code",wrapper:function(e){var n=e.children;return i.a.createElement(i.a.Fragment,{},n)}},d=i.a.forwardRef((function(e,n){var t=e.components,r=e.mdxType,a=e.originalType,s=e.parentName,l=u(e,["components","mdxType","originalType","parentName"]),f=c(t),d=r,p=f["".concat(s,".").concat(d)]||f[d]||m[d]||a;return t?i.a.createElement(p,o(o({ref:n},l),{},{components:t})):i.a.createElement(p,o({ref:n},l))}));function p(e,n){var t=arguments,r=n&&n.mdxType;if("string"==typeof e||r){var a=t.length,s=new Array(a);s[0]=d;var o={};for(var u in n)hasOwnProperty.call(n,u)&&(o[u]=n[u]);o.originalType=e,o.mdxType="string"==typeof e?e:r,s[1]=o;for(var l=2;l<a;l++)s[l]=t[l];return i.a.createElement.apply(null,s)}return i.a.createElement.apply(null,t)}d.displayName="MDXCreateElement"},149:function(e,n,t){"use strict";function r(e,n){if(null==e)return{};var t,r,i={},a=Object.keys(e);for(r=0;r<a.length;r++)t=a[r],n.indexOf(t)>=0||(i[t]=e[t]);return i}t.d(n,"a",(function(){return r}))},88:function(e,n,t){"use strict";t.r(n),t.d(n,"frontMatter",(function(){return s})),t.d(n,"metadata",(function(){return o})),t.d(n,"toc",(function(){return u})),t.d(n,"default",(function(){return c}));var r=t(147),i=t(149),a=(t(0),t(148)),s={id:"SegmentTree",title:"Segment Tree",sidebar_label:"Segment Tree"},o={unversionedId:"DataStructures/Tree/SegmentTree",id:"DataStructures/Tree/SegmentTree",isDocsHomePage:!1,title:"Segment Tree",description:"Idea",source:"@site/docs/DataStructures/Tree/SegmentTree.md",slug:"/DataStructures/Tree/SegmentTree",permalink:"/docs/DataStructures/Tree/SegmentTree",version:"current",sidebar_label:"Segment Tree"},u=[{value:"Idea",id:"idea",children:[]},{value:"Implementation",id:"implementation",children:[]},{value:"Runtime Analysis",id:"runtime-analysis",children:[]},{value:"Reference",id:"reference",children:[]}],l={toc:u};function c(e){var n=e.components,t=Object(i.a)(e,["components"]);return Object(a.b)("wrapper",Object(r.a)({},l,t,{components:n,mdxType:"MDXLayout"}),Object(a.b)("h2",{id:"idea"},"Idea"),Object(a.b)("ul",null,Object(a.b)("li",{parentName:"ul"},"This is mostly used for mutable range sum."),Object(a.b)("li",{parentName:"ul"},"For general segment tree built against a array of ",Object(a.b)("inlineCode",{parentName:"li"},"n")," length, the segment tree is ",Object(a.b)("inlineCode",{parentName:"li"},"2n")," because ",Object(a.b)("inlineCode",{parentName:"li"}," (n+n/2+n/4+n/8+\u2026+1\u22482n)")),Object(a.b)("li",{parentName:"ul"},"Segment Tree is only good when you have consistent interval updates and queries. It is not useful if you have to print or give analytics over all data points")),Object(a.b)("h2",{id:"implementation"},"Implementation"),Object(a.b)("pre",null,Object(a.b)("code",Object(r.a)({parentName:"pre"},{className:"language-java"}),"class SegmentTree  \n{ \n    int st[]; // The array that stores segment tree nodes \n    int n;\n    SegmentTree(int arr[]) { \n        n = arr.length;\n        int x = (int) (Math.ceil(Math.log(n) / Math.log(2))); \n        //Maximum size of segment tree \n        int max_size = 2 * (int) Math.pow(2, x) - 1; \n        st = new int[max_size]; // Memory allocation \n        constructTree(arr, 0, n - 1, 0); \n    } \n    \n    \n    // A recursive function that constructs Segment Tree for array[ss..se]. \n    // si is index of current node in segment tree st \n    int constructTree(int arr[], int ss, int se, int si) \n    { \n        // If there is one element in array, store it in current node of \n        // segment tree and return \n        if (ss == se) { \n            st[si] = arr[ss]; \n            return arr[ss]; \n        } \n\n        // If there are more than one elements, then recur for left and \n        // right subtrees and store the sum of values in this node \n        int mid = ss + (se - ss) / 2; \n        st[si] = constructTree(arr, ss, mid, si * 2 + 1) + \n                 constructTree(arr, mid + 1, se, si * 2 + 2); \n        return st[si]; \n    } \n\n\n    int getSumUtil(int ss, int se, int qs, int qe, int si) { \n        // If segment of this node is a part of given range, then return \n        // the sum of the segment \n        if (qs <= ss && qe >= se) \n            return st[si]; \n\n        // If segment of this node is outside the given range \n        if (se < qs || ss > qe) \n            return 0; \n\n        // If a part of this segment overlaps with the given range \n        int mid = ss + (se - ss) / 2; \n        return getSumUtil(ss, mid, qs, qe, 2 * si + 1) + \n                getSumUtil(mid + 1, se, qs, qe, 2 * si + 2); \n    } \n\n    void updateValueUtil(int ss, int se, int i, int diff, int si) { \n        // Base Case: If the input index lies outside the range of  \n        // this segment \n        if (i < ss || i > se) \n            return; \n\n        // If the input index is in range of this node, then update the \n        // value of the node and its children\n        st[si] = st[si] + diff; \n        if (se != ss) { \n            int mid = ss + (se - ss) / 2; \n            updateValueUtil(ss, mid, i, diff, 2 * si + 1); \n            updateValueUtil(mid + 1, se, i, diff, 2 * si + 2); \n        } \n    } \n\n    // The function to update a value in input array and segment tree. \n   // It uses updateValueUtil() to update the value in segment tree \n    void updateValue(int arr[], int n, int i, int new_val) \n    { \n        // Check for erroneous input index \n        if (i < 0 || i > n - 1) { \n            return; \n        } \n\n        // Get the difference between new value and old value \n        int diff = new_val - arr[i]; \n\n        // Update the value in array \n        arr[i] = new_val; \n\n        // Update the values of nodes in segment tree \n        updateValueUtil(0, n - 1, i, diff, 0); \n    } \n\n    // Return sum of elements in range from index qs (quey start) to \n   // qe (query end).  It mainly uses getSumUtil() \n    int getSum(int n, int qs, int qe) \n    { \n        // Check for erroneous input values \n        if (qs < 0 || qe > n - 1 || qs > qe) { \n            return -1; \n        } \n        return getSumUtil(0, n - 1, qs, qe, 0); \n    } \n}\n")),Object(a.b)("h2",{id:"runtime-analysis"},"Runtime Analysis"),Object(a.b)("ul",null,Object(a.b)("li",{parentName:"ul"},"Build the tree: O(n)"),Object(a.b)("li",{parentName:"ul"},"Update Tree: O(log n)"),Object(a.b)("li",{parentName:"ul"},"Query: O(log n)")),Object(a.b)("h2",{id:"reference"},"Reference"),Object(a.b)("ul",null,Object(a.b)("li",{parentName:"ul"},Object(a.b)("a",Object(r.a)({parentName:"li"},{href:"https://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/"}),"GeeksForGeeks Implement"))))}c.isMDXComponent=!0}}]);